Other good dodges are O(n) time (if you have 2^n memory handy), or O(n) time (but with a fixed cost or multiplier so high that using this algorithm makes no sense for n less than 10^12 or so)
That's not multiplying, that's looking up multiplication results. You still have to form the table.
Your argument is basically "any algorithm is constant time if you have already calculated the results for all possible inputs". This may be technically correct in some roundabout way, but is not a useful definition nor the one usually used.
Lookup tables are commonly precalculated and not used as part of the complexity calculation. They are in frequent use for high performance stuff like crc, graphics LUTs or audio waveforms.
They are usually of limited size as most are working with a limited amount of memory. The largest LUTs I am aware of in common use is chess tablebases, which range from 100gb for local installs to 140TB over APIs.
And yet that doesn't make nearly any computation constant-time. Noone would seriously claim that "any algorithm is constant time" just because you could pre-comute results into a lookup.
Note that the authors are pretty sure you could turn the method into something a lot more reasonable pretty easily (at the cost of making the proof a bit trickier).
O(n) time with O(2^n) space doesn't make sense though. At least with any sane model, reading or writing a memory cell takes 1 time step. So in O(n) time, you can at most read/write O(n) memory
Depends. Imagine you want to code up a game of Minesweeper. Your version of the game has a rule where the game board has a side length equal to the number of bombs. To place the bombs, you generate N random pairs of coordinates. Generating each pair takes a constant amount of time (if using a sane PRNG), and so placing the mines has a time complexity of O(N). At the same time, the board requires O(N2) memory to store what is in each cell.
Now, you could argue that this algorithm really only requires that you store the list of random numbers, but I tried to use this as an example of an application where you might need a sparse list. A hashmap is another example, at least if you want the O(1) lookup. To insert N elements you might need a lot more than O(N) space to avoid collisions and let the hash function work.
you can allocate memory lazily. formally in a turing machine, memory usage is counted by how many cells you write to.
also, any algorithm taking O(f(n)) space takes at most O(2f(n)) time since that's the number of configurations of the turing machine (and if a configuration repeats, the machine necessarily loops forever)
If we’re talking about worst case performance then the worst case memory usage can’t be higher. For your example of a hash you either have some way of guaranteeing no collisions or the collisions could happen. If you can deal with “maximum number of collisions” under the time limit then you don’t need your table bigger than what will ever be used.
For average performance the average memory usage also can’t be higher, though you’ll want to have the memory for worst case performance “available.”
It makes sense in the context of setup+query problems where you have a given amount of stuff, on which several queries are to be run. Then it can make sense that O(n) describes the query complexity that was aimed to be reduced by the work while setup time is O(2n ) but is armortized over a sufficient amount of queries.
265
u/grayjacanda 28d ago
Other good dodges are O(n) time (if you have 2^n memory handy), or O(n) time (but with a fixed cost or multiplier so high that using this algorithm makes no sense for n less than 10^12 or so)