1 Part I: Fundamental

Problem 1 (8 marks, 1 page). Consider the algorithm mystery() whose input consists

of an array A of n integers, two nonnegative integers P, u satisfying 0 ≤ P ≤u≤n-1, and

an integer k. We assume that n is a power of 2.

Algorithm

if P == u then

if A[P] == k then

return 1;

else

mystery(A[o.....(n − 1)], P, u, k)

-

return 0;

end if

else

m = b(P + u-1)/2];

return mystery(A, P, m, k) + mystery(A, m+ 1, u, k);

end if

a) [2 marks] What does mystery (A[0..(n-1)],0, n-1, k) compute (0.5 mark)?

Justify your answer (1.5 marks).

b) [1 mark] What is the algorithmic paradigm that the algorithm belongs to?

c) [2 marks] Write the recurrence relation for C(n), the number of additions

required by mystery(A, 0, n - 1, k).

d) [2 marks] Solve the above recurrence relation by the backward substitution

method to obtain an explicit formula for C(n) in n.

e) [1 mark] Write the complexity class that C(n) belongs to using the Big-O notation.