Space Complexity

ELI5 — The Vibe Check

Space complexity is how much extra memory your algorithm uses as the input grows. Some algorithms are super fast but eat up tons of memory; others are slower but barely use any extra space. It is the memory trade-off to time. Sometimes you trade space for speed, like caching.

Real Talk

Space complexity measures the amount of memory an algorithm requires relative to input size, expressed in Big O notation. It includes both the input space and any auxiliary space (temporary variables, data structures, call stack for recursion). A common trade-off: memoization (caching) reduces time complexity at the cost of increased space complexity.

Show Me The Code

// O(1) space — iterative sum, only one extra variable:
function sum(arr) {
  let total = 0;          // just one variable, no matter how big arr is
  for (const n of arr) total += n;
  return total;
}

// O(n) space — storing results:
function doubled(arr) {
  return arr.map(n => n * 2); // creates a NEW array of same size
}

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

When You'll Hear This

"The space complexity is O(n) because we cache all the results." / "Out-of-memory error — check the space complexity of that algorithm."