Karatsuba Multiplication

Problem: Multiply two $n$-digit numbers.

Grade school: $O(n^2)$ digit operations.

Karatsuba's insight: Split each number into two halves. $x = a \cdot 10^{n/2} + b$, $y = c \cdot 10^{n/2} + d$.

$xy = ac \cdot 10^n + (ad + bc) \cdot 10^{n/2} + bd$

This needs $4$ multiplications. Karatsuba reduces it to $3$: $(ad + bc) = (a+b)(c+d) - ac - bd$

Recurrence: $T(n) = 3T(n/2) + O(n)$

By Master Theorem: $T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})$

This beats $O(n^2)$ for large $n$. Modern libraries use even faster algorithms (Toom-Cook, FFT).