Question 1 [20 marks] A pseudocode of the binary search algorithm is given below. Algorithm BinarySearch(A[0..n 1], K) //Implements nonrecursive binary search //Input: An array A[0..n 1] sorted in ascending order and // a search key K //Output: An index of the arrays element that is equal to K // or 1 if there is no such element l 0; r n 1 while l r do

{ m [ ( l + r ) / 2 ] if K = A[m] return m else if K < A[m] r m 1 else l m + 1

}

return 1 a. [5 marks] Set up a recurrence relation for the number of key comparisons made by the binary search algorithm in the worst case C_w(n). b. [15 marks] Solve the recurrence relation C_w(n) by the backward substitution method for n = 2^_k