Consider the following recursive algorithm (SHOW FULL STEPS WITH EXPLANATION!)

C(i, j, x) that checks whether the array segment A[i..j] contains key x, where i j.

It return YES if x is found and NO otherwise (note that floor(x) is the floor function that returns the largest integer that is less than or equal to

x): C(i, j, x) if i=j then if A[i] = x return YES else return NO else if C(i, floor((i+j)/2), x) = YES return YES

else return C(floor((i+j)/2) + 1, j, x)

Let t(n) be the worst case time for C(1, n, x) and assume that n is a power of 2.

(a) Give a recurrence for t(n). Dont forget the initial condition;

(b) solve t(n) using the following methods: iteration, recursion tree, and the masters method.