Skip to interview prep
Apexed

363. How does Karatsuba multiplication beat the schoolbook O(n²) method for large integers?

HardDivide & conquer

Technical
Show model answer

Split each n-digit number into halves: x = a·B^m + b and y = c·B^m + d. Then x·y = ac·B^(2m) + (ad + bc)·B^m + bd. Schoolbook recursion needs four half-size products, ac, ad, bc and bd, giving T(n) = 4T(n/2) + O(n) = O(n²). Karatsuba notices ad + bc = (a + b)(c + d) − ac − bd, so only three products are needed.

That gives T(n) = 3T(n/2) + O(n) = O(n^(log₂ 3)) ≈ O(n^1.585), with O(n) extra space for temporaries. Real libraries switch to schoolbook below a threshold of tens of machine words and to Toom–Cook or FFT-based methods for very large numbers. It is the integer analogue of Strassen's trick.

How does Karatsuba multiplication beat the schoolbook O(n²) method for large integers — Data structures & algorithms interview question — Apexed