Solving recurrences II: the master theorem

The cookbook for divide-and-conquer recurrences

The master theorem solves any master recurrence

$$T(n)=aT(n/b)+f(n),a>0,b>1\text{constants},$$

in one of three cases. The whole method turns on comparing the driving function $f(n)$ to the watershed function $n^{{\log }_{b}a}$. That watershed counts the leaves of the recursion tree: the tree has $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ of them.

The three cases

Let $W=n^{{\log }_{b}a}$.

• Case 1 — leaves win. If $f(n)=O(n^{{\log }_{b}a-\epsilon })$ for some $\epsilon >0$ (i.e. $f$ is polynomially smaller than $W$), then $T(n)=\Theta (W)$.
• Case 2 — tie. If $f(n)=\Theta (n^{{\log }_{b}a}{\lg }^{k}n)$ for some $k\ge 0$, then $T(n)=\Theta (n^{{\log }_{b}a}{\lg }^{k+1}n)$ — the cost is shared across all levels, and one extra log factor is tacked on. The common subcase $k=0$: $f(n)=\Theta (W)$ gives $T(n)=\Theta (W\lg n)$.
• Case 3 — root wins. If $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ for some $\epsilon >0$ and the regularity condition $af(n/b)\le cf(n)$ holds for some $c<1$ and all large $n$, then $T(n)=\Theta (f(n))$.

The $\epsilon$ in cases 1 and 3 demands polynomial separation: a mere logarithmic gap between $f$ and $W$ falls outside the theorem.

Worked classifications

• $T(n)=2T(n/2)+\Theta (n)$ (merge sort): $W=n^{{\log }_{2}2}=n$, $f=\Theta (n)=\Theta (W{\lg }^{0}n)$ ⟶ case 2, $k=0$ ⟶ $\Theta (n\lg n)$.
• $T(n)=9T(n/3)+n$: $a=9,b=3$, so $W=n^{{\log }_{3}9}=n^2$; $f=n=O(n^{2-\epsilon })$ ⟶ case 1 (leaves dominate) ⟶ $\Theta (n^2)$.
• $T(n)=T(2n/3)+1$ (binary-search shape): $a=1,b=3/2$, $W=n^{{\log }_{3/2}1}=n^0=1$, $f=\Theta (1)=\Theta (W{\lg }^{0}n)$ ⟶ case 2, $k=0$ ⟶ $\Theta (\lg n)$.
• $T(n)=3T(n/4)+n\lg n$: $W=n^{{\log }_{4}3}\approx n^{0.79}$, $f=n\lg n=\Omega (n^{0.79+\epsilon })$, and regularity $3\cdot \frac{n}{4}\lg \frac{n}{4}\le \frac{3}{4}n\lg n$ holds with $c=\frac{3}{4}$ ⟶ case 3 ⟶ $\Theta (n\lg n)$.
• $T(n)=2T(n/2)+n\lg n$: $W=n$, $f=n\lg n=\Theta (n{\lg }^{1}n)$ ⟶ case 2 with $k=1$ ⟶ $\Theta (n{\lg }^{2}n)$. (Common slip: this is not $\Theta (n\lg n)$.)

The gap case — when no case applies

$T(n)=2T(n/2)+n/\lg n$: here $W=n$ and $f=n/\lg n=o(n)$, pointing toward case 1 — but $n/\lg n$ is not $O(n^{1-\epsilon })$ for any $\epsilon >0$ (it trails $n$ only by a log factor, not a polynomial one). Case 2 also fails ($f\ne \Theta (n{\lg }^{k}n)$). The recurrence falls in the gap between cases 1 and 2 and needs another tool (Akra–Bazzi gives $\Theta (n\lg \lg n)$).

Empirical check

You can't time wall-clock deterministically, but you can count the exact work merge sort does. On a reverse-sorted input each merge does $n$ moves per level over $\lg n$ levels, so total moves $=n\lg n$ exactly — and the ratio moves $/(n\lg n)$ is a flat constant as $n$ grows. The exercise below shows that constant.