logoalt Hacker News

MinimalAction • today at 12:15 AM • 4 replies • view on HN

For the uninitiated, why is this interesting given it doesn't seem to be so much below the threshold?


Replies

bawolff • today at 12:50 AM

O(n lg n) is a bit of a threshold value. For a lot of algorithms, this is the best you can do, even in theory (similar to how O(n^2) is also a threshold for many algorithms). So for many algorithms, people stop trying when they get close to O(n lg n) on the belief that you'll never do better than that.

The fact that you can in principle go faster than n lg n, even if just by an almost imperceptible amount, is kind of surprising. It raises the question of, if n lg n isn't the limit, what is? How far down can we get the speed? If we can get it a little past n lg n, maybe we can go a lot further.

[or at least that is my understanding. not a theoretical computer scientist]

Chinjut • today at 12:20 AM

It's interesting because people wondered if it was possible to go below the threshold at all, that's all. Many suspected it was not possible.

➕ show 1 reply
anvuong • today at 5:00 AM

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.