Space Complexity Basics

Space complexity measures how much extra memory an algorithm or data structure uses as the input size n grows.

While time complexity tells you how fast something runs, space complexity tells you whether it will fit in memory and how it scales with data volume.

What Counts as Space

Typically, we count:

  • Extra arrays, lists, maps, trees, etc. created by the algorithm.
  • Recursion stack depth (for recursive algorithms).

We usually ignore:

  • Space occupied by the input itself.

Example:

  • An in‑place array algorithm that only uses a few variables:
    • Extra space is O(1).
  • An algorithm that creates a dp[n] array:
    • Extra space is O(n).

Common Space Complexities

  • O(1) – constant extra memory.
    • Example: two‑pointer algorithms modifying array in place.
  • O(log n) – typical for balanced tree recursion depth.
  • O(n) – arrays/lists/maps proportional to input size.
  • O(n²) – 2D tables, e.g. DP on two strings of length n.

Space often becomes the bottleneck before time in large systems.

Data Structures and Space

Approximate overheads:

  • Arrays:
    • O(n) storage for elements, plus small constant overhead.
  • Linked lists:
    • O(n) for elements + pointers; more overhead than arrays for the same data.
  • Hash tables:
    • O(n) for entries + extra capacity to keep load factor reasonable.
  • Trees / graphs:
    • O(n) for nodes + O(m) for edges (in adjacency lists).

Trade‑offs:

  • Hash tables trade extra memory (for buckets, pointers) for O(1) expected lookup time.
  • Trees trade some memory for ordered traversal and O(log n) search.

Recursion vs Iteration

Recursive algorithms implicitly use the call stack:

  • Max recursion depth d → stack space O(d).
  • For DFS on deep trees/graphs, this can be significant.

Sometimes you can trade stack space for an explicit stack data structure, which may be easier to control and reason about.

Why Space Complexity Matters

In interviews:

  • Being aware of space usage shows maturity:
    • “This DP uses O(n²) space; we can optimize it to O(n) by keeping only two rows.”

In production:

  • Memory is a real resource:
    • Large O(n²) structures can cause out‑of‑memory errors or put pressure on GC.
    • Reducing space can improve cache locality and throughput.

Good engineers balance:

  • Time vs space.
  • Simplicity vs optimization.

Being explicit about both complexities helps you make informed trade‑offs.