 Master theorem

For divide-and-conquer recurrences $T(n)=aT(n/b)+f(n)$ with $a\ge 1$, $b>1$, compare $f(n)$ with $n^{{\log }_{b}a}$. If $f(n)=O(n^{{\log }_{b}a-\epsilon })$ for some $\epsilon >0$, then $T(n)=\Theta (n^{{\log }_{b}a})$. If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$. If $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ and $af(n/b)\le cf(n)$ for a constant $c<1$ eventually, then $T(n)=\Theta (f(n))$. Constant-size base cases and ordinary bounded rounding of subproblem sizes are understood. A recursion tree proves these cases by summing per-level costs.