Time Complexity of Multiplication
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
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.
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.