Skip to main content

Space Complexity

Space complexity measures peak live memory as a function of input size. Be explicit about whether a bound describes total memory or auxiliary space beyond the input and required output.

Memory categories​

  • Input: the representation supplied to the algorithm.
  • Output: materialized results; sometimes unavoidable and dominant.
  • Auxiliary state: tables, queues, visited sets, buffers, and temporary objects.
  • Call stack: one live frame per active recursive call.

Peak space is not the sum of every allocation made over time. Memory that is released before another phase begins does not coexist with that phase's memory.

Analysis rules​

  • Count simultaneously live objects, including hidden copies from slicing or immutable concatenation.
  • For recursion, multiply frame size by maximum active depth—not the total number of calls in the recursion tree.
  • Distinguish streamed output from a fully materialized result.
  • Include representation: adjacency matrices use Θ(V2)\Theta(V^2) while adjacency lists use Θ(V+E)\Theta(V+E).

Exponential runtime does not imply exponential stack space. A depth-first search may explore exponentially many states while retaining only a linear path plus visited or memoized state.

In-place and compression​

“In-place” usually means O(1)O(1) auxiliary storage for array rearrangement, but recursion stacks and object-level allocations can violate a casual claim. State the convention.

Dynamic-programming space can be compressed when future transitions need only a bounded frontier. Do not discard rows or predecessors needed to reconstruct the requested witness.

Time–space trade-offs​

Memoization, indexes, hashing, and precomputed tables spend memory to avoid repeated work. Recalculation, streaming, and succinct representations save memory at possible time or implementation cost. Optimize against an actual constraint, not one asymptotic dimension in isolation.

Source​