1
The three cases are which level dominates
Work per level either grows, shrinks or stays constant down the recursion tree, and log_b a against d is exactly that comparison.
Lesson · Algorithms and Complexity · Analysis
Divide and Conquer
Divide-and-conquer produces recurrences of one shape, T(n) = aT(n/b) + f(n), solved by the master theorem. The technique's power comes from reducing a, not from combining faster.
T(n) = a·T(n/b) + nᵈ
log_b a < d ⟹ Θ(nᵈ) the combining dominates
log_b a = d ⟹ Θ(nᵈ log n) every level equal
log_b a > d ⟹ Θ(n^{log_b a}) the leaves dominate
One comparison decides
Core ideas
What this lesson establishes
“Divide-and-Conquer Recurrences” in Induction and Recursion solved these recurrences; this lesson uses them to compare algorithm designs.
2
Reducing a changes the exponent
Karatsuba's improvement is three multiplications instead of four, and log₂3 < log₂4. Faster combining cannot do that.
3
Not every split is even
Quicksort's split depends on the pivot, so it has no fixed b — and its worst case is quadratic while its average is n log n.
The material
Divide and conquer
The pattern, the master theorem, and four algorithms compared.
A divide-and-conquer algorithm splits an input of size n into a subproblems of size n/b, solves each recursively, and spends f(n) dividing and combining. The running time therefore satisfies T(n) = aT(n/b) + f(n).
Theorem · Master theorem
For T(n) = aT(n/b) + Θ(nᵈ) with a ≥ 1, b > 1, d ≥ 0: T(n) = Θ(nᵈ) if log_b a < d; Θ(nᵈ log n) if log_b a = d; and Θ(n^{log_b a}) if log_b a > d.
The three cases are the recursion tree's shape. Level i holds aⁱ subproblems of size n/bⁱ, doing nᵈ(a/bᵈ)ⁱ work in total — a geometric series whose ratio a/bᵈ is below, equal to, or above 1 exactly as log_b a is below, equal to, or above d.
algorithm a b d log_b a result
binary search 1 2 0 0.000 Θ(log n)
merge sort 2 2 1 1.000 Θ(n log n)
Karatsuba multiplication 3 2 1 1.585 Θ(n^1.585)
naive matrix multiplication 8 2 2 3.000 Θ(n³)
Strassen 7 2 2 2.807 Θ(n^2.807)
closest pair of points 2 2 1 1.000 Θ(n log n)
Where the improvements come from
Karatsuba multiplies two n-digit numbers by splitting each in half. The obvious method needs four half-size products, giving T(n) = 4T(n/2) + n = Θ(n²) — no better than schoolbook multiplication. Karatsuba's identity computes the same result with three products, and log₂ 3 ≈ 1.585 < 2.
(a·10^m + b)(c·10^m + d)
= ac·10^{2m} + (ad + bc)·10^m + bd
ad + bc = (a + b)(c + d) − ac − bd ← one product, not two
so three products suffice: ac, bd, (a+b)(c+d)
Strassen does the same for matrices: seven products of half-size blocks instead of eight, giving Θ(n^{2.807}). In both cases the gain came from reducing a, and no amount of faster combining could have produced it — d only matters when it exceeds log_b a.
When the split is uneven
Quicksort partitions around a pivot, and the split depends on the data. A perfect pivot gives T(n) = 2T(n/2) + n = Θ(n log n); the worst pivot gives T(n) = T(n−1) + n = Θ(n²). The master theorem does not apply to the second, which has no fixed b at all.
Remarkably, even a badly unbalanced but constant split is fine: T(n) = T(n/10) + T(9n/10) + n is still Θ(n log n), because the recursion tree still has logarithmic depth. Quicksort survives imperfect pivots for exactly this reason, and fails only on consistently extreme ones.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Analysing a divide-and-conquer algorithm
Read off a, b, d; compare.
1
Count the recursive calls: that is a
How many subproblems, not how much smaller they are.
2
Find the shrink factor: that is b
Halving gives b = 2. If the factor varies with the data, the theorem does not apply.
3
Find the combining cost: that is nᵈ
Merging costs Θ(n) so d = 1; a constant combine gives d = 0.
4
Compare log_b a with d
Less, equal or greater. That single comparison gives the answer, and the recursion tree explains why.
Divide and conquer
Score 0 / 0Choose the answer you can justify.
Improving an algorithm two ways
Start from T(n) = 4T(n/2) + n, which is Θ(n²).
BASELINE a=4 b=2 d=1 log₂4 = 2 > 1 ⟹ Θ(n²)
Attempt 1: make the combining faster, d = 1 → d = 0
a=4 b=2 d=0 log₂4 = 2 > 0 ⟹ still Θ(n²)
NO IMPROVEMENT — the leaves already dominated.
Attempt 2: use one fewer subproblem, a = 4 → a = 3
a=3 b=2 d=1 log₂3 ≈ 1.585 > 1 ⟹ Θ(n^1.585)
A GENUINE IMPROVEMENT.
In case 3 the cost is all at the leaves, and only a affects them.
This is the structural reason Karatsuba and Strassen both take the form they do. In the leaf-dominated case the combining work is irrelevant, so the only route to a better exponent is fewer subproblems — and finding an identity that removes one is the hard creative step.
Common mistakes
1
Swapping a and ba counts subproblems and b is the shrink factor. T(n) = 3T(n/2) has a = 3, b = 2, and reversing them gives the wrong case.
2
Optimising the combining step in case 3When the leaves dominate, d is irrelevant. Effort must go into reducing a.
3
Applying the theorem to an uneven splitIt needs a fixed b. Data-dependent splits are analysed by unrolling or by the recursion tree.
Check your understanding
✓
Finish when you can say which parameter to attack.
For T(n) = 9T(n/3) + n², identify the case and say whether faster combining or fewer subproblems would help. log₃9 = 2 = d, the balanced case, where both would.
Note: The master theorem as stated covers f(n) = Θ(nᵈ). The full version handles forcing terms between the cases — n log n, for instance — and needs a regularity condition. The polynomial version covers almost every algorithm you will meet.