logoalt Hacker News

anvuong • today at 5:00 AM • 0 replies • view on HN

It shows that nlogn is not the limit, how much better we can go? Not sure, probably not much, but breaking the barrier is important. Like in marathon for years nobody thought human could break the 2 hour barrier, then someone did and now it's become normal occurrences.

Multiplication can be done by FFT, which is an exceptionally efficient algorithm that has nlogn complexity, you'd be called crazy if you claim you have something more efficient than FFT.