II (10 points) A certain algorithm has an every-case complexity function given by On our current computer we can run inputs of size n 32 in 100 nsec (nanoseconds). About how long does it take our computer to execute one ba operation? (a)% nsec (b) Y2 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 = 16 in 32 nsec, how many times faster will the new computer have to be? (a) 2 times ) 4 times (c)8 times 16 times (e) 32 times IV. (10 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/5, and the probability of finding it in the next to last position in the array is also 1/5. 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)/5 b) (3n -3)/10 (c) (7n -5)/10 d) (7n-5)/5 e) (3n -3)/5 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 20? a) 78 nsec ) 67 nsec (c) 135 nsec (d) 270 nsec (e) 114 nsec