Why Divide-and-Conquer Algorithms Need Recurrences
A divide-and-conquer algorithm, as introduced earlier in this series regarding matrix multiplication, breaks a problem of size n into smaller subproblems, solves each recursively, and combines the results. This structure naturally produces a Recurrence: an equation or inequality that describes a function in terms of its value on smaller inputs. Solving a recurrence means finding an explicit, closed-form asymptotic bound, typically expressed with the notation covered earlier in this series.
A general divide-and-conquer recurrence takes this form:
T(n) = a · T(n/b) + f(n)where a is the number of subproblems created, n/b is the size of each subproblem, and f(n) is the time spent dividing the problem and combining the subproblem solutions.
The Substitution Method: Guess and Prove
The Substitution Method involves guessing the form of the solution, then using mathematical induction to prove the guess correct. This method requires no special formula, but it does require a good initial guess, often informed by experience or a recursion-tree analysis.
As a worked example, consider proving that T(n) = 2T(n/2) + n is O(n log n). The guess is T(n) ≤ cn log n for some constant c and sufficiently large n.
Inductive hypothesis: assume T(n/2) ≤ c(n/2)log(n/2)
Substitute into the recurrence:
T(n) = 2T(n/2) + n
≤ 2c(n/2)log(n/2) + n
= cn log(n/2) + n
= cn(log n - 1) + n
= cn log n - cn + n
≤ cn log n
The last step holds whenever c ≥ 1,
since then -cn + n ≤ 0This confirms the inductive step; a separate base case argument for small n completes the proof, establishing that T(n) = O(n log n).
A common pitfall when using substitution is proving a weaker bound than needed by using an insufficiently precise inductive hypothesis. Sometimes a technique called Subtracting a Lower-Order Term is necessary: rather than guessing T(n) ≤ cn, guessing T(n) ≤ cn - b for some constant b can make the induction go through when the simpler guess fails.
The Recursion-Tree Method: Visualizing the Total Work
The Recursion-Tree Method provides a systematic way to generate a good guess for the substitution method by visualizing the recurrence as a tree, where each node represents the cost of one subproblem at one level of recursion.
Consider the recurrence T(n) = 3T(n/4) + Θ(n²). The recursion tree looks like this:
Level 0: n² — cost: n²
Level 1: (n/4)² (n/4)² (n/4)² — cost: 3(n/4)²
Level 2: 9 nodes, each (n/16)² — cost: 9(n/16)²
...continuing until subproblems reach size 1...
Level i has 3^i nodes, each of size n/4^i,
so the cost at level i is 3^i · (n/4^i)²
= n² · (3/16)^iSumming the cost across all levels, from level 0 down to the leaves, gives a geometric series:
T(n) = n² · Σ (i=0 to log₄n) (3/16)^i
Since 3/16 < 1, this geometric series converges to
a constant as the number of terms grows, bounded by:
1 / (1 - 3/16) = 16/13
Therefore T(n) = O(n²)The recursion tree reveals that the cost is dominated by the root level, since the ratio between levels shrinks geometrically. This insight — that the top level dominates — becomes the guess to verify rigorously using the substitution method described above.
The Master Method: A Direct Formula for Common Cases
The Master Method provides a fast, "cookbook" solution for recurrences of the standard divide-and-conquer form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1 are constants and f(n) is asymptotically positive. It works by comparing f(n) against n^(log_b a), the cost that recursion alone (ignoring the combine step) would produce.
Master Theorem — three cases:
Case 1: If f(n) = O(n^(log_b a - ε)) for some ε > 0,
then T(n) = Θ(n^(log_b a))
(the recursive subproblems dominate)
Case 2: If f(n) = Θ(n^(log_b a)),
then T(n) = Θ(n^(log_b a) · log n)
(recursion and combine cost are balanced)
Case 3: If f(n) = Ω(n^(log_b a + ε)) for some ε > 0,
AND the regularity condition a·f(n/b) ≤ c·f(n)
holds for some c < 1 and large n,
then T(n) = Θ(f(n))
(the combine step dominates)Applying this to the earlier matrix multiplication recurrences from this series makes the method concrete.
Naive divide-and-conquer: T(n) = 8T(n/2) + Θ(n²)
a = 8, b = 2, so n^(log_b a) = n^(log₂8) = n³
f(n) = n² = O(n^(3-ε)) for ε = 1 → Case 1
T(n) = Θ(n³)
Strassen's algorithm: T(n) = 7T(n/2) + Θ(n²)
a = 7, b = 2, so n^(log_b a) = n^(log₂7) ≈ n^2.807
f(n) = n² = O(n^(2.807-ε)) → Case 1
T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)Another common example is T(n) = 2T(n/2) + n, describing algorithms like merge sort.
a = 2, b = 2, so n^(log_b a) = n^(log₂2) = n¹ = n
f(n) = n = Θ(n^1) → Case 2 applies exactly
T(n) = Θ(n log n)Why the Master Method Has Limits
The master method does not cover every possible recurrence. There is a gap between Case 1 and Case 2, and another gap between Case 2 and Case 3, where f(n) is asymptotically larger or smaller than the comparison function but not by a polynomial factor. In these gap cases, and whenever the regularity condition in Case 3 fails, the master method simply does not apply, and the substitution or recursion-tree methods described above must be used instead.
Additionally, the master method only handles recurrences of this specific divide-and-conquer form with subproblems of equal size. Recurrences with unequal subproblem sizes, such as those arising from certain randomized algorithms discussed later in this series, require more general techniques like the Akra-Bazzi method, an extension covered in the more advanced portions of recurrence theory.
Choosing the Right Tool
In practice, the master method should be tried first for any standard divide-and-conquer recurrence, since it is by far the fastest technique when applicable. When the master method's conditions are not met, the recursion-tree method provides a systematic way to generate an educated guess about the solution's form, and the substitution method then provides the rigorous proof that the guess is correct. Together, these three techniques cover the vast majority of recurrences encountered when analyzing divide-and-conquer algorithms.