Source: wikibot/karatsuba-algorithm
= Karatsuba algorithm
{wiki=Karatsuba_algorithm}
The Karatsuba algorithm is a divide-and-conquer algorithm used for efficient multiplication of large integers. It was discovered by Anatolii Alexeevitch Karatsuba in 1960 and is particularly significant because it reduces the multiplication of two n-digit numbers from the traditional \\(O(n^2)\\) time complexity to approximately \\(O(n^\{\\log_2 3\})\\), which is about \\(O(n^\{1.585\})\\).