Time Complexity of Multiplication

Get FREE domain for 1st year and build your brand new site

Internship at OpenGenus

The Brute force Time Complexity of Multiplication operation is O(logM x logM) while the Theoretical limit of Time Complexity of Multiplication operation is O(logM x loglogM) for multiplying number number M x M.

Operation Brute Force TC Optimal TC
Multiplication O(logM x logM) O(logM x loglogM)

Beyond this point, we will assume that the numbers involved in Multiplication have N bits.

Multiplication is defined as repeated addition so if addition is O(N) time operation, then multiplication is O(N^2) time operation.

This might seem to be simple as it is the fundamental definition of multiplication, but this is not the case.

This table summarizes how the time complexity of multiplication operation improved over the years:

Algorithm Complexity Year Notes
School Multiplication O(N2) 100 BC -
Russian Peasant Method O(N2 * logN) 1000 AD -
Karatsuba algorithm O(N1.58) 1960 -
Toom Cook multiplication O(N1.46) 1963 -
Schonhage Strassen algorithm O(N * logN * loglogN) 1971 FFT
Furer's algorithm O(N * logN * 2O(log*N)) 2007 -
DKSS Algorithm O(N * logN * 2O(log*N)) 2008 Modular arithmetic
Harvey, Hoeven, Lecerf O(N * logN * 23 log*N) 2015 Mersenne primes
Covanov and ThomΓ© O(N * logN * 22 log*N) 2015 Fermat primes
Harvey and van der Hoeven O(N * logN) March 2019 Possible end

Note that the time complexity is for multiplying two N digit numbers.

It was widely believed that multiplication cannot be done in less than O(N^2) time but in 1960, the first break-through came with Karatsuba Algorithm which has a time complexity of O(N^1.58).

With recent break-through, it was thought that the theoretical limit for Multiplication will be O(N logN) but it was not proved.

Finally, in 2019, an algorithm has been developed that has a time complexity of O(N logN) for multiplication. It is a galactic algorithm which means it beats other existing algorithm only for exponentially large numbers (which are not used in practice).

Hence, we know that multiplication has a time complexity of O(N logN) while usual algorithms in practice have a time complexity of O(N^2).

With this article at OpenGenus, you must have the complete idea of Time Complexity of Multiplication. Enjoy.