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.