Master Theorem

For

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

Consider $f(n)=O(n^c)$

• If $c\le {\log }_{b}a$, $T(n)=\Theta (n^{{\log }_{b}a})$
• If $c={\log }_{b}a$, $T(n)=\Theta (n^c\log n)$
• If $c>{\log }_{b}a\wedge (\exists k<1)(af(\frac{n}{b})\le kf(n))$, $T(n)=\Theta (f(n))$