Master theorem(reprise) 7(n)=a(m/b)+f(n) CASE 1: f(n)=O(nlogba-E →(n)=(n0g) CASE 2: f(n)=o(nlogbalgkn →7(n)=( logba Ig+ln) CASE 3: f (n)=92(noga+a)and af(n/b)scf(n) →7(m)=((n) Merge sort: a=2, 6=2= noga=n →CASE2(k=0)→7m)=mnln) Day 4 Introduction to AlgorithmsDay 4 Introduction to Algorithms L3.4 Master theorem (reprise) T(n) = a T(n/b) + f(n) CASE 1: f(n) = O(nlogba – ε) ⇒ T(n) = Θ(nlogba) . CASE 2: f(n) = Θ(nlogba lgkn) ⇒ T(n) = Θ(nlogba lgk+1n) . CASE 3: f(n) = Ω(nlogba + ε) and a f(n/b) ≤ c f(n) ⇒ T(n) = Θ(f(n)) . Merge sort: a = 2, b = 2 ⇒ nlogba = n ⇒ CASE 2 (k = 0) ⇒ T(n) = Θ(n lg n)