The obvious way is quadratic
You already know how to multiply two n-digit numbers: the long multiplication you learned as a child. Each digit of one number multiplies each digit of the other, so you do about n^2 single-digit products and then add them up. That is the obvious algorithm, and it is honestly quadratic — double the digits and you quadruple the work. For decades nobody seriously believed you could do better; multiplying felt as irreducible as the digits themselves. The surprise of this guide is that the obvious cost is not the true cost, and the gap is closed by divide and conquer with one clever twist.
Let us first try divide and conquer the naive way, just to see it fail to help. Split each n-digit number into a high half and a low half: x = a * 10^(n/2) + b, and y = c * 10^(n/2) + d, where a, b, c, d are each n/2 digits long. Multiply out the product and you get x * y = a*c * 10^n + (a*d + b*c) * 10^(n/2) + b*d. The shifts by powers of ten and the additions are cheap, O(n) work. But look at the four products a*c, a*d, b*c, b*d — each is a multiplication of two half-size numbers, so we have four recursive calls on inputs of size n/2.
That gives the recurrence T(n) = 4 T(n/2) + O(n). Solve it — by a recursion tree or the master theorem — and the answer is Theta(n^2). We split, we recursed, we combined cheaply, and we got exactly the same quadratic cost as schoolbook multiplication. Dividing and conquering bought us nothing here, because the work piles up at the leaves: with four branches each halving the size, the bottom level of the tree alone already costs Theta(n^2). To actually win, we must attack the number four.
Karatsuba: three products instead of four
Here is the trick that started it all, due to Karatsuba in 1960. We need three quantities: a*c, b*d, and the middle term a*d + b*c. The naive plan computes a*d and b*c separately, costing two multiplications just for the middle. Karatsuba's insight is that we never need a*d and b*c on their own — we only need their sum. And there is an algebraic shortcut for that sum. Compute the single product (a + b) * (c + d). Multiplying it out gives a*c + a*d + b*c + b*d. We already have a*c and b*d from the other two products, so subtract them off, and what remains is exactly a*d + b*c.
p1 = a * c
p2 = b * d
p3 = (a + b) * (c + d)
middle = p3 - p1 - p2 # equals a*d + b*c, with NO extra multiply
x*y = p1 * 10^n + middle * 10^(n/2) + p2
naive split: T(n) = 4 T(n/2) + O(n) -> Theta(n^2)
Karatsuba: T(n) = 3 T(n/2) + O(n) -> Theta(n^1.585)Count the multiplications now: p1, p2, p3 — just three recursive calls on size-n/2 inputs, not four. The extra additions and subtractions are all O(n), absorbed into the combine cost. So the recurrence becomes T(n) = 3 T(n/2) + O(n). The master theorem compares the leaf work against the benchmark exponent n^(log base b of a), here n^(log base 2 of 3). Because there are now three branches instead of four, that critical exponent drops from log base 2 of 4 = 2 down to log base 2 of 3, which is about 1.585. The whole algorithm runs in Theta(n^1.585) — strictly faster than quadratic, for free, by spending one cheap addition to dodge one expensive multiplication.
Strassen: the same idea for matrices
Now play the exact same game one dimension up, with matrices. The obvious way to multiply two n-by-n matrices follows the definition: each of the n^2 entries of the result is a dot product of length n, giving Theta(n^3) scalar multiplications. Try naive divide and conquer: cut each matrix into four n/2-by-n/2 blocks. The product of two block matrices, by the usual rules, needs eight block products (each of the four result blocks is a sum of two products of half-size matrices). That is T(n) = 8 T(n/2) + O(n^2), whose critical exponent is log base 2 of 8 = 3 — back to Theta(n^3). Same story as before: blindly splitting into eight pieces buys nothing.
In 1969 Strassen pulled the Karatsuba rabbit out of the matrix hat. By forming seven cleverly chosen sums and differences of the input blocks, multiplying those to get seven products instead of eight, and then combining them with more additions, he recovers all four blocks of the answer. The seven products P1 through P7 are nothing magical to look at — combinations like (A11 + A22)(B11 + B22) — but their additions and subtractions reassemble exactly the four result blocks. As with Karatsuba, the savings comes from never computing the eight naive products separately, only the seven combinations from which the answer can be reconstructed.
Seven recursive multiplications instead of eight gives T(n) = 7 T(n/2) + O(n^2). The combine work is now O(n^2) — there are more additions of n/2-by-n/2 blocks than before — but additions of matrices are cheap relative to multiplications, and O(n^2) does not dominate. The master theorem reads off the critical exponent log base 2 of 7, about 2.807, so Strassen runs in roughly Theta(n^2.807). It is the very same lever as Karatsuba: drop the branch count by one, and the exponent that governs the leaves falls just enough to beat the obvious algorithm.
Honest fine print
It would be dishonest to leave you thinking Strassen and Karatsuba are simply better and you should always use them. The exponent does improve, but the hidden constant gets worse: Strassen's seven products come with eighteen-or-so block additions, far more bookkeeping per level than the clean eight-product naive split. Big-O hides exactly this kind of constant. Because the asymptotic advantage only shows up when n^2.807 has pulled meaningfully below n^3, the crossover happens only for large enough n — small matrices are multiplied faster the obvious way, which is why real libraries switch to schoolbook multiplication once the blocks shrink past a threshold.
And neither result is the end of the road. Karatsuba's 1.585 was the first crack in the n^2 wall; later methods using more pieces (Toom-Cook) push the exponent lower, and the Fast Fourier Transform brings big-integer and polynomial multiplication all the way down to about Theta(n log n) — a different and deeper idea covered in the next guide of this rung. For matrices, Strassen's 2.807 has been beaten repeatedly by far more intricate algorithms inching the exponent toward 2; those are theoretical landmarks with enormous constants, rarely run in practice. Karatsuba and Strassen matter not because they are the final word, but because they teach the lever: count the recursive multiplications, and remove one.
The lever, in one move
Step back and the recipe is identical in both stories. Split the problem into b-fold-smaller pieces; notice the naive method needs a recursive multiplications; find an algebraic identity that recomputes the same answer using a - 1 multiplications and some extra cheap additions; pay for those additions in the combine step. Because the leaf-dominated cost is set by the master theorem's exponent log base b of a, lowering a by one lowers the exponent — and a smaller exponent eventually wins for large inputs.
- Naive split: a recursive multiplications, recurrence T(n) = a T(n/b) + O(n^k), exponent log base b of a.
- Find an identity computing the same outputs with a - 1 multiplications and only extra O(n^k) additions.
- New recurrence T(n) = (a-1) T(n/b) + O(n^k), with the smaller exponent log base b of (a-1).
- Karatsuba: 4 -> 3 gives n^1.585; Strassen: 8 -> 7 gives n^2.807. Same lever, two arenas.
That is the lesson worth carrying forward. The obvious algorithm is not a law of nature; it is just the first thing that occurs to you. When work piles up at the leaves of a recursion, the way to win is rarely to combine more cleverly and almost always to recurse fewer times — to find the hidden algebraic identity that lets a - 1 products stand in for a. Karatsuba and Strassen are the two cleanest demonstrations that doing a little extra arithmetic to skip a single recursive call can bend an exponent.