1
$\begingroup$

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?

$\endgroup$
10

2 Answers 2

1
$\begingroup$

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".

$\endgroup$
1
  • 1
    $\begingroup$ In which computation model can you multiply integers in $O(n\log n)$? $\endgroup$ Jul 8, 2017 at 22:08
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is a circuit size lower bound. It does not translate to any nontrivial lower bound on the running time of, say, multitape Turing machines. $\endgroup$ May 26, 2023 at 14:58
  • $\begingroup$ oh I see, thanks! $\endgroup$ May 27, 2023 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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