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
Top comments (2)
The article does a good job of explaining the importance of balancing time and space complexity. The example snippets are helpful for showing O(1) and O(n) space. I'm curious how often space complexity really overshadows time complexity in a typical tech interview, though. Time constraints usually seem more important. For anyone working on DSA, prachub.com has some good resources, and their question banks match what's asked in interviews. It's worth checking out.
Thanks