3 ms·

I think "space" (i.e. in "run out of space before you can terminate") is most naturally interpreted as referring to memory.

• kazinator 2y ago
  Stack is memory! An algorithm that uses an amount of stack proportional to the input N is said to require O(N) space. If it is rewritten to explicitly allocate the storage instead of using stack, it still uses O(N) space.
  • jraph 2y ago
    Not necessarily. If you are computing an aggregation for instance, if your computation is recursive and not tail call optimized, it may overflow the stack but the fixed version will not use additional memory for each iteration. Otherwise, indeed stack is memory, but the memory in general is usually way less limited than the stack and also running out of memory doesn't have the same security implications as overflowing an unprotected stack. And, unless you manage to encode everything in the stack, your iterative version will probably take the same amount of memory as your non-optimized recursive version, minus the space used for the stack.
  • MattPalmer1086 2y ago
    True, I'd just tend to call exceeding the stack limit a stack overflow, rather than the more generic running out of space.