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?
&nbsp;
Can you please show why the fastest multiplication algorithm would have such a time complexity?
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.