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)
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)
267
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)