Space Complexity

Every algorithm uses memory. Space complexity describes how that memory usage grows with input size — the same Big-O language, applied to bytes instead of operations.

Auxiliary vs Total Space

Total space counts everything: the input itself plus any extra memory the algorithm allocates. Auxiliary space counts only the extra memory — the input is excluded because you have to store it regardless.

When someone says an algorithm runs “in O(1) space”, they almost always mean O(1) auxiliary space.

// O(1) auxiliary space — only a counter variable
function countEvens(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] % 2 === 0) count++;
  }
  return count;
}

// O(n) auxiliary space — new array proportional to input
function doubleAll(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

Recursion Stack as Space

Each recursive call pushes a stack frame. The maximum depth of the call stack is the auxiliary space used by recursion.

// O(n) stack space — n frames on the call stack
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

// O(1) auxiliary space — iterative version
function factorialIter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

Node.js defaults to a call stack limit of roughly 10,000–15,000 frames. A naive recursive Fibonacci on n = 50 would not just be slow — it would stack overflow before finishing.

In-Place Algorithms

An in-place algorithm mutates the input directly, keeping auxiliary space O(1). Array reversal is the classic example:

// In-place reverse — O(1) auxiliary space
function reverseInPlace(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const tmp = arr[lo];
    arr[lo] = arr[hi];
    arr[hi] = tmp;
    lo++;
    hi--;
  }
  return arr;
}

// Out-of-place reverse — O(n) auxiliary space
function reverseNew(arr) {
  return arr.slice().reverse();
}

In-place is not always better. Mutating the original can cause bugs in code that expected the input to be unchanged. Know the tradeoff.

Time-Space Tradeoffs

Many algorithms trade extra memory for faster time:

The hash-set duplicate finder below trades O(n) memory for O(n) time instead of O(n²) time with O(1) memory:

function hasDuplicate(arr) {
  const seen = new Set(); // O(n) auxiliary
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false;
}

In memory-constrained environments (edge functions, embedded runtimes) that extra space might be unacceptable. In most Node.js services, it is the right call.

Up Next

Theoretical complexity assumes all operations are equal. V8’s internal representation of arrays and objects affects the real-world constant dramatically.