# 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})\).