Solving recurrences II: the master theorem

The cookbook for divide-and-conquer recurrences

The master theorem solves any *master recurrence*

$$ T(n) = a\,T(n/b) + f(n), \qquad 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 - \varepsilon})$ for some $\varepsilon > 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 + \varepsilon})$ for some $\varepsilon > 0$ and the regularity condition $a\,f(n/b) \le c\,f(n)$ holds for some $c < 1$ and all large $n$, then $T(n) = \Theta(f(n))$.

The $\varepsilon$ 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-\varepsilon})$ ⟶ 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+\varepsilon})$, and regularity $3\cdot\frac{n}{4}\lg\frac{n}{4} \le \frac34 n\lg n$ holds with $c=\frac34$ ⟶ 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-\varepsilon})$ for any $\varepsilon>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.