The Master Theorem

The Recurrence Form

Many divide-and-conquer algorithms have running times described by recurrences of the form

$T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n)$

where $a \ge 1$ is the number of subproblems, $b > 1$ is the factor by which the problem size shrinks, and $f(n)$ accounts for the work of dividing and combining. We interpret $n/b$ as $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$; the asymptotic bounds are the same.

The Critical Exponent

The key quantity is the critical exponent

$c_{\text{crit}} = \log_b a$

This is the exponent of $n$ in the time contributed by the leaf level of the recursion tree. The Master Theorem compares $f(n)$ (the work done at the root and internal levels) against $n^{c_{\text{crit}}}$ (the work done at the leaves).

The Three Cases

Case 1: Leaf-Dominated

If $f(n) = O(n^{c_{\text{crit}} - \varepsilon})$ for some constant $\varepsilon > 0$, then

$T(n) = \Theta(n^{c_{\text{crit}}})$

The leaves dominate: the cost at the bottom of the tree outweighs everything above. Note the $\varepsilon$: $f(n)$ must be polynomially smaller than $n^{c_{\text{crit}}}$, not just asymptotically smaller.

Example: $T(n) = 9\,T(n/3) + n$

$a = 9$, $b = 3$, $c_{\text{crit}} = \log_3 9 = 2$. Here $f(n) = n = O(n^{2 - 0.5})$, so Case 1 gives $T(n) = \Theta(n^2)$. The $9$ subproblems at size $n/3$ generate $\Theta(n^2)$ leaf work, overwhelming the linear $f(n)$.

Case 2: Balanced

If $f(n) = \Theta(n^{c_{\text{crit}}})$, then

$T(n) = \Theta(n^{c_{\text{crit}}} \lg n)$

Each level of the recursion tree contributes the same amount of work ($\Theta(n^{c_{\text{crit}}})$), and there are $\log_b n$ levels, giving the extra $\lg n$ factor.

Example: $T(n) = 2\,T(n/2) + \Theta(n)$ (Mergesort)

$a = 2$, $b = 2$, $c_{\text{crit}} = 1$. $f(n) = \Theta(n) = \Theta(n^1)$, so Case 2: $T(n) = \Theta(n \lg n)$.

Case 3: Root-Dominated

If $f(n) = \Omega(n^{c_{\text{crit}} + \varepsilon})$ for some $\varepsilon > 0$, and the regularity condition $a\,f(n/b) \le c\,f(n)$ holds for some constant $c < 1$ and all sufficiently large $n$, then

$T(n) = \Theta(f(n))$

The root dominates: the top-level work outweighs everything below. The regularity condition ensures the work decreases geometrically down the tree: each level’s work is at most a constant fraction of the level above.

Example: $T(n) = 3\,T(n/4) + n \lg n$

$a = 3$, $b = 4$, $c_{\text{crit}} = \log_4 3 \approx 0.793$. $f(n) = n \lg n = \Omega(n^{0.793 + 0.2})$. Check regularity: $3 \cdot (n/4)\lg(n/4) = \frac{3}{4}n\lg n - \frac{3}{4}n\lg 4 \le \frac{3}{4}n\lg n$. With $c = 3/4 < 1$, regularity holds. Case 3: $T(n) = \Theta(n \lg n)$.

The Regularity Condition (Case 3)

The regularity condition $a\,f(n/b) \le c\,f(n)$ for $c < 1$ is not a formality. Without it, Case 3 can fail even when $f(n) = \Omega(n^{c_{\text{crit}} + \varepsilon})$. It rules out oscillating functions where the total cost at a child level could exceed the parent level. Most polynomially bounded functions encountered in practice satisfy it automatically.

The Polynomial Gap (ε)

The $\varepsilon > 0$ in Cases 1 and 3 means the Master Theorem requires a polynomial separation between $f(n)$ and $n^{c_{\text{crit}}}$. A logarithmic gap is not enough.

Example Where the Master Theorem Fails

$T(n) = 2\,T\!\left(\frac{n}{2}\right) + n \lg n$

$a = 2$, $b = 2$, $c_{\text{crit}} = 1$. $f(n) = n \lg n$ grows faster than $n$ but the ratio $f(n)/n = \lg n$ is not polynomial in $n^\varepsilon$ for any $\varepsilon > 0$. So $f(n) \notin \Omega(n^{1+\varepsilon})$, and $f(n) \notin O(n^{1-\varepsilon})$. The Master Theorem cannot resolve this recurrence. We must use the substitution method or the recursion-tree method instead.

This gap between Cases 2 and 3 (or between Cases 1 and 2) arises fairly rarely in practice for standard algorithmic recurrences.

The Recursion-Tree Method

When the Master Theorem cannot be applied, the recursion tree provides a fallback: expand the recurrence level by level and sum the work.

For $T(n) = 2T(n/2) + n \lg n$:

Level	Number of nodes	Problem size	Work per node	Work per level
0	1	$n$	$n \lg n$	$n \lg n$
1	2	$n/2$	$(n/2)\lg(n/2)$	$n \lg(n/2)$
2	4	$n/4$	$(n/4)\lg(n/4)$	$n \lg(n/4)$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$k$	$2^k$	$n/2^k$	$(n/2^k)\lg(n/2^k)$	$n \lg(n/2^k)$

Total work: $\sum_{k=0}^{\lg n - 1} n \lg(n/2^k) = n \sum_{k=0}^{\lg n - 1} (\lg n - k)$. This is $n$ times an arithmetic series summing to $\Theta(\lg^2 n)$, so $T(n) = \Theta(n \lg^2 n)$.

Worked Examples

Example 1: Binary Search

$T(n) = T(n/2) + \Theta(1)$

$a = 1$, $b = 2$, $c_{\text{crit}} = \log_2 1 = 0$. $f(n) = \Theta(1) = \Theta(n^0)$, so Case 2: $T(n) = \Theta(\lg n)$.

Example 2: Strassen’s Matrix Multiplication

$T(n) = 7\,T(n/2) + \Theta(n^2)$

$a = 7$, $b = 2$, $c_{\text{crit}} = \log_2 7 \approx 2.807$. $f(n) = \Theta(n^2) = O(n^{2.807 - 0.5})$, so Case 1: $T(n) = \Theta(n^{\lg 7}) \approx \Theta(n^{2.807})$.

Example 3: $T(n) = 2\,T(n/2) + \Theta(n^3)$

$a = 2$, $b = 2$, $c_{\text{crit}} = 1$. $f(n) = \Theta(n^3) = \Omega(n^{1 + 1})$. Regularity: $2 \cdot (n/2)^3 = \frac{1}{4} n^3 \le c \cdot n^3$ for $c = 1/4$. Case 3: $T(n) = \Theta(n^3)$.

Example 4: $T(n) = 3\,T(n/2) + n^2$

$a = 3$, $b = 2$, $c_{\text{crit}} = \log_2 3 \approx 1.585$. $f(n) = n^2 = \Omega(n^{1.585 + 0.3})$. Regularity: $3(n/2)^2 = \frac{3}{4}n^2 \le \frac{3}{4} n^2$. Case 3: $T(n) = \Theta(n^2)$.

Example 5: $T(n) = 8\,T(n/2) + \Theta(n^2)$

$a = 8$, $b = 2$, $c_{\text{crit}} = \log_2 8 = 3$. $f(n) = \Theta(n^2) = O(n^{3 - 0.5})$, Case 1: $T(n) = \Theta(n^3)$.

Systematic Approach to Applying the Theorem

1. Identify $a$, $b$, and $f(n)$ from the recurrence.
2. Compute $c_{\text{crit}} = \log_b a$.
3. Compare $f(n)$ against $n^{c_{\text{crit}}}$.
4. If $f(n)$ is polynomially smaller → Case 1, result $\Theta(n^{c_{\text{crit}}})$.
5. If $f(n)$ is asymptotically equal → Case 2, result $\Theta(n^{c_{\text{crit}}} \lg n)$.
6. If $f(n)$ is polynomially larger → check regularity; if satisfied, Case 3, result $\Theta(f(n))$.
7. If none of the above applies (the gap case) → use the recursion tree or substitution method.

Summary

Case	Condition	Solution	Intuition
1	$f(n) = O(n^{c_{\text{crit}} - \varepsilon})$	$\Theta(n^{c_{\text{crit}}})$	Leaves dominate
2	$f(n) = \Theta(n^{c_{\text{crit}}})$	$\Theta(n^{c_{\text{crit}}} \lg n)$	All levels equal
3	$f(n) = \Omega(n^{c_{\text{crit}} + \varepsilon})$ and regularity holds	$\Theta(f(n))$	Root dominates
Gap	$f(n)/n^{c_{\text{crit}}}$ is polylogarithmic	Not applicable	Use tree method

Example recurrence	$a,b$	$c_{\text{crit}}$	$f(n)$	Case	Result
$T(n) = 2T(n/2) + n$	2,2	1	$n$	2	$\Theta(n \lg n)$
$T(n) = 9T(n/3) + n$	9,3	2	$n$	1	$\Theta(n^2)$
$T(n) = T(2n/3) + 1$	1,1.5	0	$1$	2	$\Theta(\lg n)$
$T(n) = 3T(n/4) + n \lg n$	3,4	$\approx$0.793	$n \lg n$	3	$\Theta(n \lg n)$
$T(n) = 2T(n/2) + n \lg n$	2,2	1	$n \lg n$	Gap	$\Theta(n \lg^2 n)$