##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Solving D&C recurrences.
Master Theorem: T(n)=aT(n/b)+f(n)
Let c=logba:
1. If f(n)=O(nc−ϵ): T(n)=Θ(nc)
2. If f(n)=Θ(nc): T(n)=Θ(nclogn)
3. If f(n)=Ω(nc+ϵ): T(n)=Θ(f(n))
Merge sort: 2T(n/2)+n. a=2,b=2,c=1,f=n. Case 2: Θ(nlogn). Binary search: T(n/2)+1. a=1,b=2,c=0,f=1. Case 2: Θ(logn).
