logoalt Hacker News

these • yesterday at 4:36 PM • 3 replies • view on HN

Is n to the 1.9992 practically speaking subquadratic? Technically, yes, but is there a practically useful result here?


Replies

itishappy • yesterday at 4:41 PM

> A galactic algorithm is an algorithm with record-breaking theoretical (asymptotic) performance, but which is not used due to practical constraints. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in real-world performance. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.

https://en.wikipedia.org/wiki/Galactic_algorithm

Rudybega • yesterday at 6:51 PM

It's more that it demonstrates that it's possible at all. We now know that the floor isn't an exponent of 2, which makes pursuing further improvements way more valuable.

blovescoffee • yesterday at 4:42 PM

Yes because now it opens the door for future algorithms to chip away at that exponent where as in the past it may have seemed that an exponent of 2 was the floor.