# Lower bound on multiplication

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".
• In which computation model can you multiply integers in $O(n\log n)$? 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.