= Master theorem
For divide-and-conquer recurrences $T(n)=aT(n/b)+f(n)$ with $a\geq1$, $b>1$, compare $f(n)$ with $n^{\log_b a}$. If $f(n)=O(n^{\log_b a-\varepsilon})$ for some $\varepsilon>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+\varepsilon})$ and $af(n/b)\leq 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.
Back to article page
