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
}