Master Theorem for Divide and Conquer

For $a,b\ge 1$ and equation $T(n)=aT(n/b)+f(n)$

1. If $f(n)=O(n^{{\log }_{b}a-ϵ})$ , then $T(n)=\Theta (n^{{\log }_{b}a})$ for constant $ϵ>0$
2. If $f(n)=\Theta (n^{lo{g}_{b}a})$ , then $T(n)=\Theta (n^{{\log }_{b}a}\lg n)$
3. If $f(n)=\Omega (n^{{\log }_{b}a+ϵ})$ for constant $ϵ>0$ , and $af(n/b)\le cf(n)$ for some constant $c<1$ and large $n$ , then the answer is $T(n)=\Theta (f(n))$

Limitation:

1. In the first case, $f(n)$ must be Polynomially Smaller 多项式小于 than $n^{lo{g}_{b}a}$
2. In the third case, $f(n)$ must be Polynomially larger 多项式大于 than $n^{lo{g}_{b}a}$
3. $f(n)$ may be smaller than $n^{lo{g}_{b}a}$ but not polynomially smaller.