- The grade-school multiplication algorithm scales with O(n²), requiring more steps as numbers grow.
- Anatoly Karatsuba discovered a faster algorithm in 1960 by reducing multiplications to additions, with a runtime of O(n^1.585).
- Karatsuba's method is used in software like Python for large numbers, typically around 630 decimal digits.
- In 2019, David Harvey and Joris van der Hoeven developed an O(n × log n) algorithm, but it's only practical for 'galactic'-scale numbers.
- Theoretical computer scientists suspect O(n × log n) is the ultimate speed limit, but it remains unproven.