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, add the memory retained by all simultaneously active calls. If each frame has the same bounded size, this becomes frame size times maximum active depth. The total number of calls over the whole execution does not determine peak stack space.
• Distinguish streamed output from a fully materialized result.
• Include representation: adjacency matrices use $\Theta(V^2)$ while adjacency lists use $\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)$ 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.

Worked memory accounts

An in-place insertion sort of $n$ records retains the input array as its output. Its indexes and saved key need $O(1)$ auxiliary words; total storage is still $\Theta(n)$. Returning a separate sorted list instead requires $\Theta(n)$ output slots even before counting workspace. Count shared objects once: copying a Python list copies references, not necessarily the records they point to.

Recursive binary search with index bounds has $O(\log n)$ constant-size frames. A version that slices half the list at each call also retains copies of sizes $n/2+n/4+\cdots<n$, so auxiliary space becomes $O(n)$. The same recursion depth does not imply the same memory bound. In general sum the live frame sizes; "frame size times depth" works directly only for equally bounded frames.

For DFS on an explicit graph, a visited set can hold every reachable vertex. On an implicit search tree of depth $d$ and branching factor $b$, exploring without a global visited set can take exponential time while using $O(d)$ frames if each frame stores only a constant-size successor iterator. Saving all $b$ successors per level instead needs $O(bd)$; memoizing every explored state can require exponential memory too.

These are word/reference counts under bounded-size records, not exact bytes. Integer bit lengths, object headers, allocator overhead and delayed reclamation can change actual process memory. A peak-live-object analysis does not promise that a runtime immediately returns freed memory to the operating system.

Source

• Open Data Structures

My reading · Opened notes are remembered in this browser.