1 part i fundamental problem 1 8 marks 1 page consider the algorithm m
Question
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≤n1, 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 + u1)/2];
return mystery(A, P, m, k) + mystery(A, m+ 1, u, k);
end if
a) [2 marks] What does mystery (A[0..(n1)],0, n1, 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 BigO notation.