Space Complexity, and Why Constants Matter in Practice

Time complexity gets most of the attention because a frozen tab is immediately visible. Space complexity is quieter — it shows up as a memory tab that slowly creeps up, or a mobile browser that kills your page for using too much RAM — but it's measured with exactly the same tools, and it matters just as much once your data gets real.

Auxiliary space: what you allocate, not what you're given

Space complexity asks: how much extra memory does an algorithm use, beyond the input it was handed? That extra memory is called auxiliary space, and it's the number you actually report — not the size of the input itself, which you didn't choose to allocate.

function doubled(arr) {
  const out = [];
  for (const x of arr) out.push(x * 2);
  return out;
}

arr is the input — you don't count it. out is a new array that grows to match arr's length, one new number per input element. That's O(n) auxiliary space.

Compare that to a version that mutates in place:

function doubleInPlace(arr) {
  for (let i = 0; i < arr.length; i++) arr[i] *= 2;
  return arr;
}

No new array. A constant handful of loop variables regardless of how big arr is. That's O(1) auxiliary space — the classic trade of mutating your input (not always allowed, not always safe, but genuinely cheaper) for memory you don't have to pay for.

This exact trade-off — a fresh array/object versus mutating in place — comes up constantly in frontend code, especially in React, where "don't mutate state" is the rule and "but a fresh copy costs memory and a render" is the bill you pay for following it. Neither choice is free; know which one you're making.

The hidden space cost: the call stack

Here's the one people miss, because it doesn't look like an allocation at all:

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

No array, no object, nothing that looks like memory. And yet this function's space complexity is O(n), not O(1) — because every call to factorial that hasn't returned yet stays on the call stack, waiting for the call below it to finish and hand back a value. Call factorial(1000) and, at the deepest point, there are 1,000 stack frames alive simultaneously, each holding its own copy of n. That's real memory, held for real, and it's exactly why very deep recursion can crash with Maximum call stack size exceeded — a topic this course returns to properly once trees and deep DOM structures are on the table.

An iterative version avoids this entirely:

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

One result variable, one i. O(1) space, regardless of n. Same answer, same time complexity (O(n) either way), genuinely different space cost. This is a real trade you'll make deliberately later in this course.

Why constants and real data size matter more in practice than in theory

Big-O deliberately throws away constant factors, because it's answering "does this get qualitatively worse as data grows" — and for that question, constants are noise. But once you're choosing between two options that have the same Big-O, the constants are the entire remaining question, and Big-O has nothing left to say about it.

A hash map lookup and a binary search over a sorted array are both, loosely, close to O(1) versus O(log n) — different classes, sure, but the comparison that actually matters day to day is often narrower: two O(n) approaches to the same problem, one of which does simple array reads and one of which does property lookups on freshly-allocated objects, can differ by a large constant factor in practice because of things Big-O doesn't model at all — CPU cache locality, garbage collector pressure, how V8 happens to optimize a particular loop shape.

None of that means Big-O is wrong. It means Big-O answers one question (will this survive 100x the data) and benchmarking answers a different one (which of these two same-shape options is actually faster right now). Using the wrong tool for either question is how you end up either shipping an O(n²) bug that only shows up in production, or spending an afternoon micro-optimizing an O(1) function that runs once per page load and was never the bottleneck.

What to remember

• Space complexity measures auxiliary memory — what the algorithm allocates beyond its input — using the same drop-constants, keep-the-dominant-term rules as time complexity.
• The call stack is memory. A recursive function with n unreturned calls has O(n) space complexity even if it never touches an array or object.
• Mutating in place trades away a fresh allocation for a real constraint (you can't do it to data someone else still needs); know which you're choosing and why.
• Big-O intentionally drops constants to describe growth shape — which makes it the wrong tool for choosing between two options of the same Big-O class. That comparison is a benchmarking question, not an asymptotic one.