Space Complexity

Space Complexity

Space complexity measures how much extra memory your code needs as the input grows. It's the other side of the performance coin — time complexity tells you how fast it runs, space complexity tells you how much RAM it eats.

Imagine you're moving apartments. Time complexity is how long it takes to pack. Space complexity is how many boxes you need. Sometimes you can pack faster by using more boxes, or save boxes by taking more time. That's the trade-off between time and space.

Just like time complexity, we use Big O to describe space complexity. O(1) means constant space — you use the same amount of memory no matter what. O(n) means you create data structures that grow proportionally with the input.

O(1) vs O(n) Space

O(1) space means you're just using a few variables. No matter if the array has 10 elements or 10 million, you're not creating anything extra. O(n) space means you're building a new array or object that scales with the input size.

Look at these two functions. Both reverse an array, but one uses O(1) space and the other uses O(n). The first one modifies the original array directly. The second one creates a brand new array — extra memory for every element.

function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    const temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
  return arr;
}

function reverseCopy(arr) {
  const reversed = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    reversed.push(arr[i]);
  }
  return reversed;
}

console.log(reverseInPlace([1, 2, 3, 4, 5]));
console.log(reverseCopy([1, 2, 3, 4, 5]));

The Time-Space Trade-off

Here's the thing — you often can't have both the fastest time and the smallest space. Caching results? That takes memory but speeds things up. Recalculating on the fly? That saves memory but costs time. It's a balancing act.

The right choice depends on your constraints. Building for a tiny embedded device? Optimize space. Building a real-time app? Optimize time. Understanding both lets you make informed decisions instead of guessing.