Back to Catalog
Big O
Acceptable
O(n) - Linear Space
Memory grows proportionally with input — trading RAM for speed is often worth it.
Intent & Description
Real-world Use Case
Deduplication — store all seen elements in a Set (O(n) space) to get O(1) lookup per element. Memoization in dynamic programming — cache results in a Map to avoid recomputation. Both deliberately trade memory for speed.
Source
📌 TL;DR
O(n) space = RAM grows with input. Common and usually fine. Watch for stack overflow on recursive O(n) depth. When memory is tight, look for in-place O(1) space alternatives.
Advantages
- Often enables faster time complexity — O(n) space can turn O(n²) time into O(n)
- Natural and readable — storing results is intuitive
- Modern machines have plenty of RAM — O(n) space is usually fine for in-memory workloads
- Enables powerful patterns like memoization, frequency maps, and index tables
Disadvantages
- At scale (n = 100M+) — O(n) space can mean gigabytes of RAM
- Heap allocations create GC pressure in managed languages (JS, Java, Python)
- Copying large data structures just for processing is wasteful if avoidable
- Deep recursion stacks (n levels) cause stack overflow for large n — use iteration instead
Implementation Example
// O(n) space — Hash set for O(1) dedup lookup
function removeDuplicates(arr) {
return [...new Set(arr)]; // Set stores up to n elements — O(n) space
}
// O(n) space — Memoization trades space for time (O(n) time vs O(2^n) naive)
function fib(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n); // O(1) lookup
const result = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, result); // Store up to n results — O(n) space
return result;
}
// O(1) space alternative — when memory matters more than elegance
function fibIterative(n) {
if (n <= 1) return n;
let a = 0, b = 1;
for (let i = 2; i <= n; i++) [a, b] = [b, a + b]; // Only 2 variables — O(1) space
return b;
}
// O(n) space recursion — watch for stack overflow on large n
function sumRecursive(n) {
if (n === 0) return 0;
return n + sumRecursive(n - 1); // Call stack depth = n — stack overflow at ~10k-100k
}