The Master Theorem for Divide-and-Conquer Recurrences

Statement

Let \(T : \mathbb{N} \to \mathbb{R}_{\ge 0}\) satisfy the divide-and-conquer recurrence \[ T(n) = a \, T(n/b) + f(n), \] where \(a \ge 1\), \(b > 1\) are constants and \(f : \mathbb{N} \to \mathbb{R}_{\ge 0}\). Let \(\alpha = \log_b a\) (the critical exponent). Then (Cormen et al. 2009):

  • Case 1 (leaves dominate): if \(f(n) = O(n^{\alpha - \epsilon})\) for some \(\epsilon > 0\), then \(T(n) = \Theta(n^\alpha)\).
  • Case 2 (balanced): if \(f(n) = \Theta(n^\alpha \log^k n)\) for some \(k \ge 0\), then \(T(n) = \Theta(n^\alpha \log^{k+1} n)\).
  • Case 3 (root dominates): if \(f(n) = \Omega(n^{\alpha + \epsilon})\) for some \(\epsilon > 0\) and the regularity condition \(a f(n/b) \le c f(n)\) holds for some \(c < 1\) and all sufficiently large \(n\), then \(T(n) = \Theta(f(n))\).

We assume floors and ceilings in \(n/b\) do not change the asymptotic behavior — a standard fact for these recurrences.

Recursion-tree picture

Unfold the recurrence as a tree. The root has cost \(f(n)\). Each node at depth \(i\) has \(a^i\) copies, each on input of size \(n / b^i\), contributing \(a^i \, f(n / b^i)\) at that level. The recursion bottoms out at depth \(\log_b n\), where the leaves have cost \(\Theta(1)\) each. The number of leaves is \(a^{\log_b n} = n^{\log_b a} = n^\alpha\), contributing \(\Theta(n^\alpha)\) total leaf cost.

So the total cost is \[ T(n) = \Theta(n^\alpha) + \sum_{i=0}^{\log_b n - 1} a^i \, f(n / b^i). \]

The three cases of the master theorem correspond to which part of this sum dominates.

Diagram: where the cost lives in each case

The same recursion tree is shown three times, with bar widths proportional to the cost contributed at each level. In Case 1 cost grows toward the leaves; in Case 2 every level contributes equally; in Case 3 the root dominates.

Case 1: leaves dominate e.g. T(n) = 4T(n/2) + n leaves level 0: n level 1: 2n level 2: 4n level 3: 8n T(n) = Θ(n²) leaf count = a^d = n² Case 2: balanced e.g. T(n) = 2T(n/2) + n n n n n level 0 level 1 level 2 leaves T(n) = Θ(n log n) log n levels × n per level Case 3: root dominates e.g. T(n) = 2T(n/2) + n² n² n²/2 n²/4 leaves T(n) = Θ(n²) geometric sum dominated by root Bar widths are proportional to total cost at each level. Which level dominates the geometric sum determines the asymptotic answer.

Assume \(f(n) \le C n^{\alpha - \epsilon}\) for some constants \(C, \epsilon > 0\) and all sufficiently large \(n\).

Bound the level-\(i\) contribution: \[ a^i \, f(n / b^i) \le a^i \cdot C (n / b^i)^{\alpha - \epsilon} = C n^{\alpha - \epsilon} \cdot \frac{a^i}{b^{i(\alpha - \epsilon)}} = C n^{\alpha - \epsilon} \cdot b^{i \epsilon} \] using \(a^i = b^{i \alpha}\).

Summing over \(i = 0, \dots, \log_b n - 1\): \[ \sum_i a^i \, f(n/b^i) \le C n^{\alpha - \epsilon} \cdot \frac{b^{\epsilon \log_b n} - 1}{b^\epsilon - 1} = C n^{\alpha - \epsilon} \cdot \frac{n^\epsilon - 1}{b^\epsilon - 1} = O(n^\alpha). \]

So the non-leaf contribution is \(O(n^\alpha)\), and adding the leaf cost \(\Theta(n^\alpha)\) gives \(T(n) = \Theta(n^\alpha)\).

The matching \(\Omega(n^\alpha)\) lower bound comes from the leaves alone.

Proof of Case 2: balanced cost

Assume \(f(n) = \Theta(n^\alpha \log^k n)\) for some \(k \ge 0\). The level-\(i\) contribution is \[ a^i \, f(n / b^i) = \Theta\left( a^i \cdot (n/b^i)^\alpha \log^k(n/b^i) \right) = \Theta\left( n^\alpha \log^k(n/b^i) \right), \] using \(a^i (n/b^i)^\alpha = n^\alpha\).

Summing over \(i = 0, \dots, \log_b n - 1\): \[ \sum_i \Theta(n^\alpha \log^k(n/b^i)) = \Theta\left( n^\alpha \sum_i \log^k(n/b^i) \right). \]

Substituting \(j = \log_b n - i\) so that \(\log(n/b^i) = j \log b\): \[ \sum_{j=1}^{\log_b n} (j \log b)^k = \Theta\left( (\log b)^k \cdot \log_b^{k+1} n \right) = \Theta(\log^{k+1} n). \]

So \(T(n) = \Theta(n^\alpha) + \Theta(n^\alpha \log^{k+1} n) = \Theta(n^\alpha \log^{k+1} n)\).

Proof of Case 3: root dominates

Assume \(f(n) = \Omega(n^{\alpha + \epsilon})\) for some \(\epsilon > 0\), and the regularity condition \(a \, f(n/b) \le c \, f(n)\) for some \(c < 1\) and all \(n \ge n_0\).

The regularity condition iterates: for any \(i \ge 0\), \[ a^i \, f(n / b^i) \le c^i \, f(n). \]

Summing over \(i = 0, \dots, \log_b n - 1\): \[ \sum_i a^i \, f(n/b^i) \le f(n) \sum_{i=0}^\infty c^i = \frac{f(n)}{1 - c} = O(f(n)). \]

Combined with the matching root contribution \(f(n)\) at \(i = 0\), the total non-leaf cost is \(\Theta(f(n))\). Since \(f(n) = \Omega(n^{\alpha + \epsilon})\) dominates the leaf cost \(n^\alpha\), we conclude \(T(n) = \Theta(f(n))\).

The regularity condition is necessary: without it, \(f\) could oscillate badly enough that the geometric sum of level costs does not telescope.

Worked applications

Recurrence \(\alpha\) \(f(n)\) Case \(T(n)\)
\(T(n) = 2 T(n/2) + n\) (mergesort) \(1\) \(n\) 2, \(k = 0\) \(\Theta(n \log n)\)
\(T(n) = T(n/2) + 1\) (binary search) \(0\) \(1\) 2, \(k = 0\) \(\Theta(\log n)\)
\(T(n) = 2 T(n/2) + 1\) \(1\) \(1\) 1 \(\Theta(n)\)
\(T(n) = 3 T(n/2) + n\) (Karatsuba) \(\log_2 3\) \(n\) 1 \(\Theta(n^{\log_2 3})\)
\(T(n) = 7 T(n/2) + n^2\) (Strassen) \(\log_2 7\) \(n^2\) 1 \(\Theta(n^{\log_2 7})\)
\(T(n) = 2 T(n/2) + n^2\) \(1\) \(n^2\) 3 (regularity holds: \(2 (n/2)^2 = n^2/2\)) \(\Theta(n^2)\)

Beyond the master theorem

The master theorem covers only \(T(n) = a T(n/b) + f(n)\). Recurrences with subtractive structure (\(T(n) = T(n - 1) + f(n)\)), uneven splits (\(T(n) = T(n/3) + T(2n/3) + n\)), or non-constant \(a\) require other techniques: substitution, the recursion-tree method, or the Akra–Bazzi theorem (a much more general formula for divide-and-conquer recurrences with arbitrary fractional splits).

References

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. 3rd ed. MIT Press. https://mitpress.mit.edu/9780262533058/introduction-to-algorithms/.