What is the worst-case time complexity of the Karatsuba algorithm for multiplying two n-digit numbers?

O(n^log2(3))

Karatsuba is a divide-and-conquer algorithm that reduces four sub-multiplications to three. Its complexity is approximately O(n^1.585), significantly faster than the O(n^2) schoolbook multiplication.