alt Hacker NewsThe site is taking forever to load but complexity theory doesn't really have the hard walls at things like O(nlogn) that people seem to think.
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.
Replies
Wouldn't it take an infinite lookup table to do this satisfying any two integers and still get an order-complexity speedup? The integers can be any size. You can't specify an arbitrarily variable sized lookup table in the normal formulation of these problems without computing the lookup table as part of the computation.
[dead]
> You can always always tradeoff time vs space
Not always, isn't it? The theorem says that there exists a function that can be sped up, but not that every function can be. A trivial counter example would be the identity function on a TM. It's simply a HALT/ACCEPT. There's no way to reduce that.
The space/time trade-off is also not infinitely flexible, since it takes time to fill space. And lookup tables have to be constructed at run-time, or they'll be of finite size, and hence only a constant speed-up. Perhaps you were thinking of that theorem, the linear as wikipedia calls it? https://en.wikipedia.org/wiki/Linear_speedup_theorem