# O(n) - Linear Space

> Memory grows proportionally with input — trading RAM for speed is often worth it.

- **Category**: Big O
- **Subcategory**: complexity
- **Canonical URL**: https://designpattern.fyi/big_o/linear-space/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
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.



## Implementation Example

```javascript
// 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
}

```



## Trade-offs


### 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




### Considerations & Drawbacks

- 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







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)