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.

Fig: 1