Karatsuba multiplication

Karatsuba multiplication multiplies two $n$-digit integers using three, rather than four, multiplications of roughly half-size. Its recurrence $T(n)=3T(n/2)+O(n)$ gives $T(n)=O(n^{{\log }_{2}3})$.