Master Method for Recursive Complexities

Method §

The formal definition of the master method is given for a recurrence relation of the form

$$T(n)=aT(\frac{n}{b})+f(n)$$

where $a\ge 1,b>1$ and $f(n)$ is an asymptotically positive function, as

$$T(n)=\{\begin{array}{rlr}& & \\ & \Theta (n^{{\log }_{b}a})& \text{if}f(n)=O(n^{{\log }_{b}a-ϵ})\text{ for some }ϵ>0\\ & \Theta (n^{{\log }_{b}a}{\log }_{k+1}n)& \text{if}f(n)=\Theta (n^{{\log }_{b}a}{\log }_{k}n)\text{ for some }k\ge 0\\ & \Theta (f(n))& \text{if}f(n)=\Omega (n^{{\log }_{b}a+ϵ})\text{ for some }ϵ>0\text{ and }\\ & & af(\frac{n}{b})\le kf(n)\text{ for large }n\text{.}\end{array}$$

Example §

Given a recurrence relation

$$T(n)=T(\frac{2n}{3})+1$$

we compute $lo{g}_{b}a=lo{g}_{\frac{3}{2}}1=0$. As $f(n)=O(1)$ and $n^{{\log }_{b}a}=n^0$, case 2 applies. Therefore $T(n)=\Theta (\log n)$.