Strassen’s surprising matrix multiplication, and the three methods for solving the recurrences that divide-and-conquer keeps producing.
Chapter 2 solved one recurrence by drawing a tree and squinting. Chapter 4 turns that into machinery. It opens with matrix multiplication, where a naive divide-and-conquer gains nothing and a clever one beats the Θ(n³) barrier that stood for centuries, then spends the rest of its length on substitution, recursion trees, and the master method — three ways to solve T(n) = aT(n/b) + f(n). The master method in particular becomes a lookup table you will use for the rest of the book.
lgᵏ n factors, so it now covers recurrences the 3rd edition left in the gap between cases. A new final section adds the Akra-Bazzi method for recurrences with unequal subproblem sizes. There is also a much more careful treatment of what a recurrence means for small n.A recurrence is an equation that describes a function in terms of its value on smaller inputs. Divide-and-conquer produces them automatically: if an algorithm splits into a subproblems of size n/b and spends f(n) dividing and combining, then
T(n) = a·T(n/b) + f(n)f(n) is called the driving function. The whole chapter is about extracting a closed form from this shape.
T(n) = Θ(1) for all n below some threshold, because every real algorithm bottoms out in constant time on constant-size input. Second, you may ignore floors and ceilings. Writing T(n/2) instead of T(⌈n/2⌉) and T(⌊n/2⌋) never changes the asymptotic answer for the recurrences that arise in practice.Both shortcuts are justified in the chapter rather than assumed. The reason they are safe is the same: they perturb the function only by a constant factor or on finitely many small inputs, and asymptotic notation is blind to both. But they are shortcuts, not identities — the chapter shows a contrived recurrence where dropping the floor changes the answer, as a reminder that the licence has limits.
Given two n × n matrices A and B, the product C = A·B is defined entry by entry:
cᵢⱼ = ∑ from k=1 to n of aᵢₖ · bₖⱼThe definition translates straight into three nested loops.
MATRIX-MULTIPLY(A, B, C, n)
1 for i = 1 to n
2 for j = 1 to n
3 for k = 1 to n
4 cᵢⱼ = cᵢⱼ + aᵢₖ · bₖⱼThree nested loops of n iterations each, constant work inside: Θ(n³). Note this version accumulates into an existing C rather than returning a new matrix.
For a long time Θ(n³) looked like the natural cost — there are n² output entries and each is a dot product of length n. The interesting question is whether that reasoning is actually a lower bound. It is not.
Assume n is an exact power of 2. Partition each matrix into four n/2 × n/2 submatrices:
Each of the eight submatrix products is a recursive call on size n/2. Adding two n/2 × n/2 matrices costs Θ(n²). So
T(n) = 8T(n/2) + Θ(n²)The master method will say this is Θ(nlog₂8) = Θ(n³). All that recursion bought exactly nothing.
a, not from the mere act of recursing. With a = 8 and b = 2, log₂8 = 3 and you are back where you started. Get a down to 7 and the exponent becomes log₂7 ≈ 2.81.Strassen’s 1969 insight was that you can compute the four quadrants of C using only seven multiplications instead of eight, at the price of many more additions and subtractions. Since additions cost Θ(n²) and multiplications drive the recursion, trading additions for a multiplication is a good deal.
The method has four steps. First, form 10 sums and differences of quadrants:
S₁ = B₁₂ - B₂₂ S₆ = B₁₁ + B₂₂
S₂ = A₁₁ + A₁₂ S₇ = A₁₂ - A₂₂
S₃ = A₂₁ + A₂₂ S₈ = B₂₁ + B₂₂
S₄ = B₂₁ - B₁₁ S₉ = A₁₁ - A₂₁
S₅ = A₁₁ + A₂₂ S₁₀ = B₁₁ + B₁₂Then compute seven products recursively — this is the only place recursion happens:
P₁ = A₁₁ · S₁ P₅ = S₅ · S₆
P₂ = S₂ · B₂₂ P₆ = S₇ · S₈
P₃ = S₃ · B₁₁ P₇ = S₉ · S₁₀
P₄ = A₂₂ · S₄Finally, assemble the quadrants by adding and subtracting the Ps:
C₁₁ = P₅ + P₄ - P₂ + P₆
C₁₂ = P₁ + P₂
C₂₁ = P₃ + P₄
C₂₂ = P₅ + P₁ - P₃ - P₇Verifying that these expand to the right quadrants is pure algebra — substitute the definitions and watch the unwanted terms cancel. CLRS does one; the rest are exercises. What nobody can supply is intuition for where the seven products came from. The book is candid about this: Strassen found them, and the reason such a set exists is not obvious.
The recurrence has a = 7 now:
T(n) = 7T(n/2) + Θ(n²) → T(n) = Θ(nlg 7) = O(n2.81)| Naive / block D&C | Strassen | |
|---|---|---|
| Recursive multiplications | 8 | 7 |
| Additions of submatrices | 4 | 18 |
| Recurrence | 8T(n/2) + Θ(n²) | 7T(n/2) + Θ(n²) |
| Running time | Θ(n³) | Θ(nlg 7) ≈ Θ(n2.81) |
S and P matrices. And the naive triple loop is exceptionally cache-friendly and vectorises beautifully, which the RAM model cannot see. Crossover is typically in the hundreds or low thousands of rows, so tuned libraries use blocked naive multiplication and reach for Strassen only for very large dense matrices, if at all. It remains theoretically important: it proved Θ(n³) was not the answer, and started a chase for the true exponent that has since pushed below 2.372.The substitution method is guess the form of the answer, then prove it by induction. It is the most powerful of the three because it can handle any recurrence, and the most demanding because you have to supply the guess.
Substitution method
1. Guess the form of the solution, with unspecified constants.
2. Verify by mathematical induction.
3. Solve for the constants that make it work.T(n) = 2T(⌊n/2⌋) + Θ(n)Guess T(n) = O(n lg n), that is, T(n) ≤ cn lg n for some constant c > 0 and all n past a threshold. Assume it holds for all smaller values, in particular for ⌊n/2⌋:
T(n) ≤ 2·( c·⌊n/2⌋·lg(⌊n/2⌋) ) + dn // d from the Θ(n)
≤ 2·( c·(n/2)·lg(n/2) ) + dn
= cn·lg(n/2) + dn
= cn·lg n - cn·lg 2 + dn
= cn·lg n - cn + dn
≤ cn·lg n // provided c ≥ dThe induction goes through whenever c ≥ d. The base case is handled by choosing c large enough to cover the finitely many small n, which is always possible since each is a fixed constant.
T(n) ≤ cn and the algebra leaves you with cn + 1, strengthen the hypothesis to T(n) ≤ cn - d for a constant d > 0. Counter-intuitively, proving something stronger makes the induction work, because the extra -d gives you slack to absorb the residue. This surprises people every time and it is the single most useful technique in the section.T(n) = 2T(⌊n/2⌋) + n, someone “proves” T(n) = O(n): assume T(⌊n/2⌋) ≤ c⌊n/2⌋, then T(n) ≤ 2c⌊n/2⌋ + n ≤ cn + n = O(n). Wrong. The inductive hypothesis was T(n) ≤ cn for that specific constant c, and cn + n is not ≤ cn. Hiding the failure inside the O at the last step is the error. You must reproduce the hypothesis exactly, with the same constant, or the induction proves nothing.A recursion tree makes the cost structure visible. Each node is the non-recursive cost of one subproblem; the total is the sum over all nodes. Chapter 2 used one informally for merge sort; here is the standard harder example.
T(n) = 3T(n/4) + cn²T(n) = 3T(n/4) + cn². Unlike merge sort’s tree, the levels are not equal: each is 3/16 of the one above, so the root dominates.Reading it off:
d there are 3ᵈ nodes, each of size n/4ᵈ, so the level costs 3ᵈ·c(n/4ᵈ)² = (3/16)ᵈ·cn².4ᵈ = n, so the tree has log₄n + 1 levels and 3log₄n = nlog₄3 leaves.∑ (3/16)ᵈ cn² plus the leaf cost Θ(nlog₄3).Since 3/16 < 1, the series converges and is bounded by cn²/(1 - 3/16) = (16/13)cn². And log₄3 ≈ 0.79, so the leaves contribute only Θ(n⁰·⁷⁹), which is dwarfed. Hence T(n) = O(n²), and since the root alone costs cn², also Ω(n²). So T(n) = Θ(n²).
Θ(f(n)). Balanced: every level costs the same, answer is that cost times the number of levels. Leaf-heavy: level costs increase geometrically, the leaves dominate, answer is Θ(nlogᴸa).CLRS recommends using a recursion tree to generate a guess, then verifying it with substitution. The tree can be sloppy — approximations and dropped floors are fine — because the substitution proof is what makes it rigorous.
The master method is a cookbook. It solves recurrences of one specific shape without any thinking, which is why it is the one you will actually use.
a > 0 and b > 1 be constants and f(n) a driving function that is defined and non-negative on all sufficiently large reals. Define T(n) = aT(n/b) + f(n). Then the asymptotic behaviour of T(n) is determined by comparing f(n) against the watershed function nlogᴸa.Everything turns on that comparison. nlogᴸa is the total cost of the leaves; f(n) is the cost of the root. Whichever wins, wins.
| Case | Condition on f(n) | Solution | Who dominates |
|---|---|---|---|
| 1 | f(n) = O(nlogᴸa - ε) for some constant ε > 0 |
T(n) = Θ(nlogᴸa) |
Leaves. f is polynomially smaller. |
| 2 | f(n) = Θ(nlogᴸa · lgᵏ n) for some constant k ≥ 0 |
T(n) = Θ(nlogᴸa · lgk+1 n) |
Every level equally. Pick up one extra lg. |
| 3 | f(n) = Ω(nlogᴸa + ε) for some ε > 0, and the regularity condition a·f(n/b) ≤ c·f(n) holds for some c < 1 and large n |
T(n) = Θ(f(n)) |
The root. f is polynomially larger. |
f(n) = Θ(nlogᴸa) exactly, giving Θ(nlogᴸa lg n). The 4th edition generalises it to allow any lgᵏ n factor with k ≥ 0, so recurrences such as T(n) = 2T(n/2) + n lg n are now covered directly — case 2 with k = 1 gives Θ(n lg² n). That recurrence fell in the gap between cases in the 3rd edition and needed a recursion tree.“Polynomially smaller” is a real requirement. Cases 1 and 3 do not merely ask that f be smaller or larger than the watershed — they ask that it differ by a factor of nᵉ for some fixed ε > 0. A logarithmic factor is not enough. This is why there are gaps between the cases where the theorem simply does not apply.
T(n) = 2T(n/2) + n/lg n. Here log₂2 = 1, so the watershed is n. Is f(n) = n/lg n polynomially smaller than n? No — it is smaller only by a logarithmic factor, and n/lg n is not O(n1-ε) for any ε > 0. It is not case 2 either, since lg⁻¹ n is not lgᵏ n for k ≥ 0. The master theorem does not apply, and you fall back to a recursion tree, which gives Θ(n lg lg n).The regularity condition in case 3 is not decoration. It requires that f shrink by at least a constant factor when its argument is divided by b, which is what guarantees the level costs form a decreasing geometric series. Every polynomially-bounded f you will meet satisfies it, so in practice you check it and move on — but there are pathological f that satisfy the Ω condition and fail regularity, and for those the theorem gives no answer.
The procedure is mechanical: compute logᴸa, write down the watershed nlogᴸa, compare f(n) to it, read off the case.
| Recurrence | a, b | Watershed nlogᴸa | f(n) vs it | Case | T(n) |
|---|---|---|---|---|---|
T(n) = 2T(n/2) + Θ(n) | 2, 2 | n¹ = n | equal, k=0 | 2 | Θ(n lg n) — merge sort |
T(n) = 8T(n/2) + Θ(n²) | 8, 2 | n³ | smaller by n | 1 | Θ(n³) — block matrix multiply |
T(n) = 7T(n/2) + Θ(n²) | 7, 2 | nlg7 ≈ n²·⁸¹ | smaller | 1 | Θ(nlg7) — Strassen |
T(n) = 3T(n/4) + cn² | 3, 4 | n⁰·⁷⁹ | larger by n¹·² | 3 | Θ(n²) |
T(n) = T(n/2) + Θ(1) | 1, 2 | n⁰ = 1 | equal, k=0 | 2 | Θ(lg n) — binary search |
T(n) = 2T(n/2) + n lg n | 2, 2 | n | equal × lg n, k=1 | 2 | Θ(n lg² n) |
T(n) = 4T(n/2) + n³ | 4, 2 | n² | larger by n | 3 | Θ(n³) |
T(n) = 9T(n/3) + n | 9, 3 | n² | smaller by n | 1 | Θ(n²) |
Two recurrences that look like they should fit but do not, and are worth recognising:
T(n) = T(n-1) + Θ(1) — subtracts rather than divides, so it is not of master-method form at all. It unrolls directly to Θ(n). Same for T(n) = T(n-1) + Θ(n) = Θ(n²), which is the worst case of quicksort.T(n) = T(n/3) + T(2n/3) + Θ(n) — the subproblems have different sizes, so a and b are not defined. A recursion tree gives Θ(n lg n), and the next section gives a general tool.New in the 4th edition. The Akra-Bazzi method handles recurrences where the subproblems are not all the same size:
T(n) = ∑ from i=1 to k of aᵢ·T(n/bᵢ) + f(n)Find the unique real p satisfying ∑ aᵢ/bᵢp = 1. Then, under mild conditions on f,
T(n) = Θ( np · ( 1 + ∫ from 1 to n of f(x)/xp+1 dx ) )For T(n) = T(n/3) + T(2n/3) + Θ(n): solve (1/3)ᵖ + (2/3)ᵖ = 1, which gives p = 1. The integral of x/x² from 1 to n is ln n, so T(n) = Θ(n(1 + ln n)) = Θ(n lg n), matching the recursion tree.
k = 1 and it reproduces all three cases. It is more general and more work, so use the master method when it applies and reach for this when the splits are uneven. It also explains why quicksort with a guaranteed constant-fraction split is Θ(n lg n) regardless of how lopsided the constant is, which is the key insight of Chapter 7.| Method | Use when | Cost |
|---|---|---|
| Master method | The recurrence is aT(n/b) + f(n) and f is not in a gap | Seconds. Always try this first. |
| Recursion tree | You need a guess, or the master method does not apply | Minutes. Gives intuition, not rigour. |
| Substitution | You have a guess and need a proof, or the recurrence is irregular | Most work. Always available. |
| Akra-Bazzi | Subproblems have different sizes | Requires an integral. General. |
T(n) = aT(n/b) + f(n). You may omit the base case and ignore floors and ceilings; neither changes the asymptotic answer for real algorithmic recurrences.8T(n/2) + Θ(n²) = Θ(n³) — recursing alone buys nothing. The win comes from reducing the subproblem count.Θ(nlg7) ≈ Θ(n²·⁸¹). Theoretically decisive, rarely used in practice because of constants, stability, and cache behaviour.O is the classic invalid proof.Θ(f(n))), balanced (equal levels, multiply by depth), or leaf-heavy (geometric increasing, answer Θ(nlogᴸa)).f(n) to the watershed nlogᴸa. Polynomially smaller → case 1, equal to within lgᵏ n → case 2 (gain one lg), polynomially larger plus regularity → case 3. Gaps exist; 2T(n/2) + n/lg n is the standard one.∑ aᵢ/bᵢᵖ = 1, then integrate.Chapter 5 closes Part I by adding randomness. It develops the probabilistic tools — indicator random variables above all — needed to analyse algorithms whose behaviour depends on random choices, and shows how randomising the algorithm converts a dependence on lucky input into a guarantee that holds for every input. That machinery is what makes randomized quicksort in Chapter 7 work.