Recurrence for binary search 7(n)=17(m/2)+⊙(1 subproblems work dividing subproblem size and combining nlogba=nlog2=n=1= CASE 2(k=0) →7(m)=⊙(lgn) Day 4 Introduction to Algorithms L3.11Day 4 Introduction to Algorithms L3.11 Recurrence for binary search T(n) = 1 T(n/2) + Θ(1) # subproblems subproblem size work dividing and combining nlogba = nlog21 = n0 = 1 ⇒ CASE 2 (k = 0) ⇒ T(n) = Θ(lg n)