Space Complexity Explained

Every other post in this series has been about time — how many operations an algorithm does. This one is entirely about the other question: how much extra memory it needs while it runs. Algorithm Complexity Explained introduces the auxiliary-vs-total distinction briefly; this post is the full, code-first treatment — what O(1) through O(n²) space actually look like, the recursion trap that catches people who've otherwise mastered time complexity, and why the same function can have a wildly different growth rate for time than it does for space.

The habit: count what gets allocated, not what's already there

The input itself doesn't count. If a function takes an array of n numbers and returns their sum, that array's O(n) memory existed before the function was ever called — the function's space complexity is about what it allocates in addition to the input, formally called auxiliary space. A single running total variable is O(1) auxiliary space, regardless of how large the input array is. This is the same distinction covered in Algorithm Complexity Explained, restated as the practical question worth asking while reading code: what new memory does this line create, and does its size depend on n?

O(1) space — a fixed number of variables

function reverseInPlace(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]]; // swap, no new array
    left++;
    right--;
  }
  return arr;
}

Two pointers and a temporary swap — the same three variables exist whether arr has 10 elements or 10 million. Nothing here scales with n, so it's O(1) auxiliary space, even though the function is clearly O(n) time (it still has to visit every element once). That gap between the two numbers isn't a mistake — it's completely normal, and it's the entire reason time and space get analyzed as two separate questions in the first place.

O(n) space — new memory proportional to the input

function uniqueValues(nums) {
  const seen = new Set();      // grows with the input — up to n entries
  const result = [];           // could also grow to n entries
  for (const num of nums) {
    if (!seen.has(num)) {
      seen.add(num);
      result.push(num);
    }
  }
  return result;
}

Both the Set and the result array can hold up to n entries in the worst case (an input with no duplicates) — that's O(n) auxiliary space. This is the same shape as a memoization cache, or the hash map from When O(n²) Becomes a Problem — trading O(n) space for a faster lookup than scanning would allow, on purpose.

O(n²) space — memory that scales with every pair

This shows up whenever a data structure's size depends on n × n instead of just n — the clearest example is representing a graph as an adjacency matrix instead of an adjacency list:

function adjacencyMatrix(n, edges) {
  const matrix = Array.from({ length: n }, () => new Array(n).fill(0)); // n × n cells, always
  for (const [a, b] of edges) {
    matrix[a][b] = 1;
    matrix[b][a] = 1;
  }
  return matrix;
}

function adjacencyList(n, edges) {
  const list = Array.from({ length: n }, () => []); // n arrays, total size grows with edges, not n²
  for (const [a, b] of edges) {
    list[a].push(b);
    list[b].push(a);
  }
  return list;
}

The matrix allocates n² cells no matter how many edges the graph actually has — even a graph with almost no edges still pays for the full grid. The list only stores what's actually there: O(V + E) total across every node's list, which is why Graph Traversal Visualizer and Shortest Path Visualizer both represent their graphs as adjacency lists — a real, deliberate space-complexity choice, not an arbitrary implementation detail.

The trap: recursion depth is space too

This is the one that catches people who are otherwise completely comfortable with space complexity — a recursive function can be O(n) space with no explicit data structure anywhere in it, purely because of how many stack frames are alive at once.

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Naive recursive Fibonacci makes O(2ⁿ) calls in total — fib(15) alone makes 1,973 calls, verified by running the actual trace in Recursion vs Iteration Visualizer. But its space complexity is only O(n), not O(2ⁿ) — at any single moment, only the calls along one path from the root to the deepest base case are on the stack simultaneously; every call that has already returned has freed its frame. Time counts every call that ever happened. Space only counts what's alive right now. That's not a coincidence or an approximation — it's the two questions actually measuring different things, the same way Algorithm Complexity Explained covers case and notation as genuinely independent axes rather than two names for the same idea.

Memoizing doesn't remove this cost — it adds to it. A cache large enough to hold every fib(k) for k up to n is another O(n), on top of the O(n) recursion depth that's still there. Two separate O(n) costs side by side add, they don't multiply — O(n) + O(n) = O(n), same class either way, which is exactly why memoized Fibonacci is described as O(n) time and O(n) space, not O(n²) anything.

In-place vs. not — six sorting algorithms, three different answers

"In-place" means O(1) auxiliary space — the algorithm rearranges the input using (at most) a constant amount of extra memory, instead of building a new structure the size of the input. Sorting Algorithm Visualizer makes the real spread concrete:

Cheat sheet: pattern → space complexity

Try it yourself

Sorting Algorithm Visualizer shows exactly which of six real sorting algorithms sort in place and which don't, and Recursion vs Iteration Visualizer shows a real call stack growing and shrinking frame by frame — the most direct way to actually see O(n) recursion depth instead of taking it on faith. Both run entirely in your browser.

FAQ

Is space complexity ever more important than time complexity?

On memory-constrained hardware (embedded systems, mobile, anything processing data larger than available RAM), yes, directly — an algorithm that's asymptotically faster but needs more memory than the machine has isn't actually usable. See Time Complexity Interview Guide for how this shows up as a specific, commonly-asked interview constraint.

Does output size count toward space complexity?

Conventionally no, the same way input size doesn't — a function that has to return an O(n)-sized result isn't charged for memory that was going to exist regardless of how the function is implemented. What counts is the extra working memory used to produce that output, which is exactly what "auxiliary space" means.

Is anything on this page sent anywhere?

No — this is a static guide, and every tool linked from it runs entirely in your browser.