Question

(a) Write the recurrence relation for Binary Search, using the formula T(n) = aT(n/b) + D(n) + C(n). (We'll assume T(1) = C, where c is some constant, and you can use c to represent other constants as well, since we can choose c to be large enough to work as an upper bound everywhere it is used.) (b) Draw the recursion tree for Binary Search, in the style shown in screencast 2E and in Figure 2.5 of CLRS. (Don't just copy the example for Merge Sort: it will be incorrect. Make use of the recurrence relation you just wrote!) (c) Using a format similar to the counting argument in Figure 2.5 of the text or of screencast 2E, use the tree to show that Binary Search is O(lg n) in the worst case. Specifically, 1. show what the row totals are, 2. write an expression for the tree height (and justify it), and 3. use this information to determine the total computation represented by the tree.

Example from screen cast

Answer 1

DC) con & CON) I(n) = (n/) tc to divide time Subproblem size we don't, to L combine Subproblem med results T(n) = TCH/2) to nal otherwise C 7 Ton) Each lend has constant costa Tân Thanh) * Tức) Táo) , Tang) Ć , TC/2x) & T Cry m) TCD) T (2) cu oci.ow con Problem diuision cost free

1. #rows = K = depth of recursion. logn = logo t k log 2 (K=logn, 2. = depth of recursion=k h= logn) 3. at each function level call i cost of constant- Hence, Time complexity = #Function calls T(h) = Olign) TM) é colgn