III (10 points) A certain algorithm has an every-case complexity function given by T(n) - (nlgn). On our current computer we can run inputs of size n 8 in 48 nsec (nanoseconds). About how long does it take our computer to execute one basic operation? (a) 4 nsec (b) i nsec (c) 1 nsec (d) 2 nsec (e) 4 nsec If we bought a faster computer so that we could run this algorithm on n nsec, how many times faster will the new computer have to be? 16 in 16 (a) 2 times (b) 4 times (c) 8 times (d) 16 times (e) 32 times IV. (15 points) We are running Sequential Search on an array of size n, and we know that the item we are searching for is definitely present in the array. The probability of finding it in the last position in the array is 1/3, and the probablity of finding it in the next to last position in the array is also 1/3. The probabilities of matching the search key with each of the other items are all equal. The average case complexity function for Sequential Search under these conditions, A(n)- (a) (2n - 1)/3 (b) (3n -3)/6 (c) (5n-3)/6 (d) (7n- 5)/3 (e) (3n-5)/6 If our current computer can execute one basic operation (one comparison) in 10 nsec, what would be the expected average running time on an array of size 15? (a) 78 nsec (b) 67 nsec (c) 135 nsec (d) 270 nsec (e) 120 nsec