liveBook · Manning

Space complexity

As explained in Algorithms Every Programmer Should Know

A measure of how an algorithm's memory usage grows as a function of input size.

Suppose an algorithm works well on a small input but runs out of memory on a large one. Space complexity describes how the memory it needs grows as the input grows. It sits alongside time complexity when comparing algorithms, especially where inputs are large or memory is limited. section 1.3.1 section 1.3

Ask what the algorithm must keep while it runs: stored elements, a queue or stack, a set of visited nodes, or a table of results. Then relate that storage to input size using Big O notation. A fast operation does not necessarily mean small overall memory use. section 1.3 section 1.3.1 section 1.4.3

A few examples make the scale easier to see:

  • A stack holding N elements has O(N) space complexity, even though pushing or popping its top element takes O(1) time. section 1.4.3
  • Breadth-first search of a tree uses a queue that can hold an entire level: O(W) space for maximum width W. Depth-first search uses O(D) space for maximum depth D. section 1.4.4
  • Breadth-first and depth-first graph traversals use a visited set to prevent cycling back through nodes. That set can grow to V vertices, giving the stated O(V) space bound. section 1.4.5
Figure 1.11 Traversal paths shown through a network with a cycle. Left: Depth-First Search (DFS) traces deep pathways until it detects dead-ends and mismatches. Right: A Breadth-First Search (BFS) expands to all neigboring or adjacent nodes. Both traversals use a visited set to track already visited nodes to avoid infinite loops.

The traversal paths show why both searches must remember visited nodes when a graph contains a cycle. section 1.4.5

When a table becomes too large

A two-dimensional knapsack table has O(n×W) space complexity, where n is the number of items and W is the capacity limit. Even with few items, a very large W can make the table impractical. Because each calculation uses values from the preceding row, a one-dimensional array can reduce memory use for this formulation. section 7.3

The representation matters too. Floyd–Warshall keeps one V×V distance grid and has O(V²) space complexity; it can update that grid without retaining every earlier version. Push–Relabel has O(V²) space with static capacity and flow matrices, or O(V+E) with adjacency lists. When choosing an approach, check both its memory bound and the quantities that make that bound grow. section 9.1 section 10.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines memory use, works through storage bounds for data structures and traversals, and explains table-size limits and a memory optimization.
Examples
Uses stacks, tree and graph traversals, a knapsack table, and shortest-path and flow algorithms to illustrate memory growth.
What it assumes
Introduces the metric from basic algorithm analysis and explains bounds through familiar data structures rather than assuming advanced mathematics.
What you can do after
Evaluate/understand memory costs and choose between stored data structures, table sizes, and representations under input constraints.
How it connects
Connects Big O notation and time complexity with stacks, graph traversal, dynamic programming, and graph representations.

Also explained in

Compare how 5 books explain space complexity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.