Consider the following algorithm and answer the questions:

ALGORITHM W(A,l,r,K)

//Input: A is an array of sorted integers

// l and r are the leftmost and rightmost indexes of the array elements to be processed

// K is an integer

if l > r return -1

else

m <- floor((l+r)/2)

if K = A[m] return m

else if K < A[m] return W(A, l, m-1, K)

else return W(A, m+1, r, K)

1. What does the algorithm compute?

2. How is input size n expressed in terms of parameters?

3. Assume that after comparison of K with A[m], the algorithm can determine whether K is smaller than, equal to, or larger than A[m]. Set up a recurrence (with an initial condition) for comparison in the worst case of this algorithm. Solve the recurrence for n = 2k, and determine the efficiency class.

4. What is the efficiency class when n = 2k? Why?