Space Complexity

Memory grows too

Space complexity measures how much extra memory an algorithm needs as the input grows, using the same Big O notation as time. An algorithm that allocates a copy of the input is O(n) space; one that uses a few variables regardless of input size is O(1) space.

Auxiliary vs total space

• Auxiliary space — the extra memory the algorithm itself allocates (temporaries, recursion frames).
• Total space — auxiliary space plus the input itself.

Usually we care about auxiliary space, since the input is given and not under our control.

In-place algorithms

An algorithm is in-place if it uses O(1) auxiliary space — it rearranges the input without allocating a full copy. Quicksort is in-place (apart from recursion frames); merge sort is not, because it allocates a temporary array of size n during the merge step.

// In-place reverse — O(1) space
for (int i = 0; i < n / 2; i++)
  swap(arr[i], arr[n - 1 - i]);

// Not in-place — allocates a copy, O(n) space
int[] reversed = new int[n];
for (int i = 0; i < n; i++)
  reversed[i] = arr[n - 1 - i];

The hidden space cost of recursion

Every recursive call adds a frame to the call stack. A recursive function with depth O(n) uses O(n) stack space — even if it allocates no other memory:

// O(n) time, O(n) space (stack depth = n)
int sum(int n) {
  if (n == 0) return 0;
  return n + sum(n - 1);
}

// O(n) time, O(1) space — same result, no stack growth
int sum = 0;
for (int i = 1; i <= n; i++) sum += i;

Recursion's elegance has a memory price. Deep recursion on large inputs can exhaust the stack where an equivalent loop would run in constant space. Always ask: "could this be a loop?"

Time–space tradeoffs

You can often trade memory for speed. Memoizing Fibonacci turns O(2ⁿ) time into O(n) time — at the cost of an O(n) table. Hash-based lookups trade O(n) memory for O(1) access. Caching trades repeated computation for stored state. The best choice depends on which resource is scarcer in your system.