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
🎯 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
More...
⚡ 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
| 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
More...