patternModerate
Proof that no O(n) multiplication algorithm exists
Viewed 0 times
multiplicationalgorithmthatexistsproof
Problem
For the multiplication of two $n$ digit numbers, the best known algorithm has complexity $O(n \log n)$. Has it been proven that this is the best possible, or that an algorithm $O(n)$ is not possible?
Solution
There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.
Context
StackExchange Computer Science Q#126725, answer score: 13
Revisions (0)
No revisions yet.