Space complexity and the cost of the call stack

Extra memory counts, and recursion spends it whether you notice or not.

Lesson 9 of 75 · Beginner 2 min read

Space complexity measures the extra memory an algorithm needs as the input grows — the input itself is not counted, since you were given it. This is called auxiliary space, and it is what interviewers mean by "can you do it in O(1) space?".

// O(1) auxiliary space: two numbers, whatever n is.
function sum(items) {
  let total = 0;
  for (const item of items) total += item;
  return total;
}

// O(n) auxiliary space: the map grows with the input.
function counts(items) {
  const seen = new Map();
  for (const item of items) seen.set(item, (seen.get(item) ?? 0) + 1);
  return seen;
}

Recursion spends memory you did not allocate

Every pending call holds a stack frame. The depth of the recursion is the space cost.

// O(n) space: n frames stacked before any of them returns.
function sumTo(n) {
  return n === 0 ? 0 : n + sumTo(n - 1);
}

At n = 100,000 this throws RangeError: Maximum call stack size exceeded. The loop version does the same work in O(1) space. A recursive solution is never O(1) space, however tidy it looks.

This is why tree recursion is quoted as O(h), where h is the height: O(log n) for a balanced tree, O(n) for a degenerate one.

The classic trade

Most speed-ups are memory purchases:

Approach	Time	Space
Nested loops to find a pair summing to a target	O(n²)	O(1)
Hash map of complements	O(n)	O(n)
Sort, then two pointers	O(n log n)	O(1) if sorted in place

None is universally right. On a memory-constrained device the O(n²) version may be the correct answer; in a request handler it is not.

Say both numbers

State time and space together, always: "O(n) time, O(n) space — I am trading memory for a single pass." Naming the trade shows you know it exists, which is most of what the question is testing.