I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?
Can you please show why the fastest multiplication algorithm would have such a time complexity?


Multiplication of n-bit integers can be done in $O (n \log n)$ if you are a bit careless in calculating the complexity, for example using convolution and FFT. You need $O (n \log n)$ floating point operations, but as n grows larger, you need to increase (very slowly) the precision of the floating-point operations, which will increase the complexity a little bit.

It is very well possible that no algorithm can be faster than $O (n \log n)$. It is a bit more possible that we will never find such an algorithm. However, I'm not aware of anything coming even close to a proof.

Proofs for lower bounds that turn out to be actually achieved are usually either very simple or nonexistent. For example the proof that sorting n items using comparisons takes $O(n \log n)$ is quite simple. When someone writes "multiplication cannot be done faster than $O(n \log n)$", that most likely means "I have not the slightest idea how this could be done".

  • 1
    $\begingroup$ In which computation model can you multiply integers in $O(n\log n)$? $\endgroup$ – Yuval Filmus Jul 8 '17 at 22:08

There is a lower bound for multiplication of $\Omega(n\log{n})$ conditional on a conjecture in network coding. There is also an algorithm matching this bound.

New contributor
Manuel Cáceres is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.