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})$$.