Karatsuba Algorithm
Karatsuba algorithm is a fast multiplication algorithm with time complexity \(O(n^{\log_2 3}) \approx O(n^{1.58})\).
The basic idea is divide-and-conquer:
This requires 4 multiplications each step, which doesn’t improve the time complexity. The insight is:
This requires 3 multiplications instead of 4 each step and reduces time complexity from \(O(n^2)\) to \(O(n^{\log_2 3})\).