Space Complexity Explained

Space complexity is the amount of memory an algorithm uses, expressed as a function of input size n, using the same Big-O notation as time complexity. An algorithm that allocates a new array of size n has O(n) space complexity; one that only ever uses a fixed number of variables, regardless of n, has O(1) space complexity.

See the Big-O Cheat Sheet for the same complexity classes applied to space instead of time — the growth-rate reasoning is identical.

This is the distinction that trips up most learners. Input spaceis the memory used to store the input itself — you don’t get to opt out of it, and it’s not really “used” by the algorithm’s logic. Auxiliary space is everything else the algorithm allocates beyond the input to do its work — temporary arrays, extra variables, a recursion call stack.

When people say an algorithm sorts “in place” with O(1) space, they mean O(1) auxiliaryspace — the input array itself still occupies O(n), but the algorithm doesn’t allocate anything new beyond it. Space complexity discussions almost always mean auxiliary space unless stated otherwise; this guide does the same from here on.

function reverseInPlace(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
  return nums;
}
// Auxiliary space: O(1) — only left, right, and a swap use extra memory
// (the input array itself is O(n), but that's input space, not auxiliary space)

Compare the in-place reversal above to a version that builds a new array instead of mutating the input:

function reverseCopy(nums) {
  const result = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    result.push(nums[i]);
  }
  return result;
}
// Auxiliary space: O(n) — result grows to hold all n elements

Same time complexity — O(n) either way — but very different space complexity. This is a real, common tradeoff: the copying version is safer (it doesn’t mutate the caller’s data) at the cost of O(n) extra memory.

Every recursive call adds a new frame to the call stack, and each frame consumes memory until it returns. That makes the recursion’s depth — not the number of calls — the relevant quantity for space complexity.

function sum(nums, i = 0) {
  if (i >= nums.length) return 0;
  return nums[i] + sum(nums, i + 1);
}
// n recursive calls, and they're all on the stack simultaneously
// (the outermost call can't return until the innermost one does)
// Auxiliary space: O(n) — one stack frame per element, all live at once

This is why an iterative version of the same function has O(1) auxiliary space even though the recursive version doing the “same” logic is O(n) — the loop reuses one set of variables instead of stacking a new frame per iteration.

Divide-and-conquer recursion that halves its input each call — like binary search’s recursive form — only ever has O(log n) frames on the stack at once, because the recursion depth is the number of halvings, not the number of elements.

“In-place” means the algorithm rearranges the input using only a constant amount of extra memory, rather than building new data structures. This is a real tradeoff between sorting algorithms:

• Quicksort partitions the input array in place, so its auxiliary space is just the recursion stack — O(log n) on average, O(n) in the worst case.
• Merge sort is not in place — its merge step builds new arrays to hold merged results, costing O(n) auxiliary space regardless of how balanced the recursion is.

Neither approach is universally “better” — merge sort trades memory for a time-complexity guarantee that never degrades, while quicksort trades a worst-case risk for lower memory use in the common case.

• Counting input space as if it were auxiliary space.Every algorithm that touches an n-element array “uses” O(n) memory in some sense — but calling every such algorithm O(n) space erases the distinction that actually matters: what the algorithm allocates beyond the input.
• Forgetting the recursion stack entirely. It’s easy to see a recursive function that returns a single number and assume O(1) space, missing that the stack itself grows with recursion depth.
• Assuming lower time complexity implies lower space complexity, or vice versa.They’re independent axes — merge sort’s better worst-case time complexity comes with worse space complexity than quicksort’s, not better.
• Ignoring output space.If a function is required to return a new n-element structure, that memory is arguably unavoidable output — worth naming explicitly (e.g. “O(n) auxiliary space excluding the required output”) rather than folding it silently into “O(1) space.”

• How to Analyze Time Complexity of Any Algorithm — the equivalent step-by-step method for time, including the loop/recursion patterns referenced above.
• Binary Search — O(1) iterative vs. O(log n) recursive space, a direct example of the recursion-stack point above.
• Merge Sort — O(n) auxiliary space from the merge step, not in place.
• Quicksort — in-place partitioning, O(log n) to O(n) space depending on pivot luck.