Auto Research: Integer multiplication below n log n(app.getsupers.com) |
Auto Research: Integer multiplication below n log n(app.getsupers.com) |
You can always always tradeoff time vs space. It's actually a fundamental part of complexity theory called Blums speedup theorem by the guy who invented complexity theory no less.
As an example you give me an nlogn solution and i take a portion of the inner loop, put it in a lookup table (who cares if the lookup table is 2^n in size, that's not what we're measuring here since we're specifically measuring time not space) and suddenly i have something better than nlogn since that lookup table is O(1).
That's not to say there's some merit to all of this. It's just that people shouldn't be as astonished by these results as they are. It's complexity theory. There's literally no such thing as a hard wall where something is nlogn in time and can't get lower. It can always get lower. But you need both the time and space complexities together to reason about this.
https://nitter.kareem.one/RohanArun/status/21093360158149592...
(Replace top-level with healthy instances or x.com as needed)
You don't need to go to these extremes regardless though. For small speedups take an nlogn algorithm and just move a very small part of the inner portion out in a similar tradeoff. Eg. "Every nth input is now part of a lookup." If you look at the openAIs <nlogn results there was a series of small improvements of this type (we take this part out, precomputing it, and likewise with this part and that small portion, aha! <nlogn!). I finally loaded the link above and it's 262million lines of such tricks in fact.