HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Proof that no O(n) multiplication algorithm exists

Submitted by: @import:stackexchange-cs··
0
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.