n (digits): 100
Move cursor across chart
At n = 100:
Naive: 10,000
Karatsuba: 1,000
Speedup: 10×
Key values
| n | Naive | Kara | Speed |
|---|
| 10 | 100 | 45 | 2.2× |
| 100 | 10,000 | 1,000 | 10× |
| 1,000 | 1,000,000 | 31,623 | 32× |
| 10k | 100M | 1M | 100× |
Complexity:
Naive: O(n²)
Karatsuba: O(n^log₂3) = O(n^1.585)
Crossover: n ≈ 20