Space Complexity Explained — Why Memory Matters in DSA

Fast code that crashes on 1 million inputs because it's eating all the RAM is still broken code. That's space complexity.

⚡ What is Space Complexity?

It measures how much memory an algorithm uses relative to input size — expressed in Big-O notation.

📦 Auxiliary Space (What We Measure)

The extra memory beyond the input — variables, arrays, recursion stack.

📊 Common Space Complexities

O(1) — Constant Space

function sum(arr) {
  let total = 0; // 1 variable, regardless of arr size
  for (let x of arr) total += x;
  return total;
}

O(n) — Linear Space

function copyArray(arr) {
  return [...arr]; // New array grows with input
}

O(n) — Recursion Stack

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1); // n frames on call stack
}

⚖️ Time vs Space Trade-off

Approach	Time	Space
Caching results	O(1) lookup	O(n) storage
Recalculating	O(n)	O(1)
In-place sort	Same	O(1)
Merge sort	O(n log n)	O(n) extra

🎯 Interview Tip

Always state both complexities: "O(n) time and O(1) space" — this shows complete thinking.

---

Part 5 of the Bitveen DSA Series. Originally published at bitveen.com