Harvard University Programming Recurrences Question

Question 2: Recurrences
(a) Below is the pseudo-code for two algorithms: Practicel(A,s,f) and Practice2(A,s,f), which take as
input a sorted array A, indexed from s to f. The algorithms make a call to Bsearch(A,s,f,k) which we
saw in class. Determine the worst-case runtime recurrence for each algorithm: Ti(n) and T2(n). Show that
Ti(n) is O(log n)?) and T2(n) is O(n log n).
Practicel(A,s,f)
if s< q1 = [(8 + f)/2] if BSearch(A,s,q1,1) = true return true else return Practicel(A, q1+1, f) else return false Practice2(A,s,f) if s < f if BSearch(A,s+1,f,1) = true return true else return Practice2(A, s, f-1) else return false to each of the following, or state that it does not apply: . (b) Apply the master theorem T(n) = T(n/3) + n log n • T(n) = 16T(n/4) + n1.5 log n T(n) = 4T(n/16) + Vn. = . (c) The recursive algorithm below takes as input an array A of distinct integers, indexed between s and f, and an integer k. The algorithm returns the index of the integer k in the array A, or -1 if the integer k is not contained within A. Complete the missing portion of the algorithm in such a way that you make three recursive calls to subarrays of approximately one third the size of A. • Write and justify a recurrence for the runtime T(n) of the above algorithm. • Use the recursion tree to show that the algorithm runs in time O(n). 2 FindK(A,s,f,k) if s < f if f =s +1 if k = A[s] return s if k = A[f] return f else ql = [(2s + f)/3] q2 = [(q1+1+1)/2] to be continued. else to be continued.