# Time and Space Complexity — Part 2: Space Complexity and Trade-offs

## 1. What Space Complexity Measures

Space complexity describes how much **extra memory** an algorithm needs, relative to input size — beyond the input itself. It uses the same Big-O notation as time complexity.

```js
function sumArray(arr) {         // O(1) space — one accumulator variable, regardless of arr's size
  let total = 0;
  for (const n of arr) total += n;
  return total;
}

function doubleAll(arr) {         // O(n) space — allocates a NEW array of the same size
  return arr.map(n => n * 2);
}

function doubleInPlace(arr) {      // O(1) space — mutates the existing array, no new allocation
  for (let i = 0; i < arr.length; i++) arr[i] *= 2;
  return arr;
}
```

## 2. The Classic Time-Space Trade-off

Using extra memory (space) can often reduce time complexity, and vice versa — this trade-off shows up constantly in real algorithm design.

```js
// O(n²) time, O(1) extra space — checks every pair
function hasDuplicateSlow(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(n) time, O(n) extra space — trades memory (a Set) for speed
function hasDuplicateFast(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}
```

This exact trade-off is the reasoning behind the Hashing topic's hash tables: spend O(n) extra memory to turn O(n) lookups into O(1) lookups.

## 3. Recursive Functions and Call Stack Space

Every recursive call adds a frame to the call stack — recursive algorithms have space complexity proportional to their **maximum recursion depth**, not just their data structures.

```js
function sumRecursive(arr, i = 0) {  // O(n) time, O(n) SPACE — n stack frames deep at the worst point
  if (i >= arr.length) return 0;
  return arr[i] + sumRecursive(arr, i + 1);
}

function sumIterative(arr) {          // O(n) time, O(1) space — no growing call stack
  let total = 0;
  for (const n of arr) total += n;
  return total;
}
```

A deep enough recursive call (tens of thousands of frames on a large array) can throw `RangeError: Maximum call stack size exceeded` — this is a direct, practical consequence of recursion's O(depth) space cost.

## 4. Worked Example: Analyzing a Real Function

```js
function findPairsSummingTo(arr, target) {
  const seen = new Set();          // O(n) space, worst case
  const pairs = [];                // O(n) space, worst case
  for (const num of arr) {          // O(n) time — single pass
    const complement = target - num;
    if (seen.has(complement)) pairs.push([complement, num]); // O(1) average lookup
    seen.add(num);                  // O(1) average insert
  }
  return pairs;
}
// Total: O(n) time, O(n) space
```

Compare this to a naive nested-loop version checking every pair: O(n²) time, O(1) extra space — the same time-space trade-off from section 2, applied to a real problem (this is exactly the "two sum" pattern from the Hashing topic's exercises).

## 5. Under the Hood: Why Real-World Constants Don't Match the Theory

Big-O deliberately ignores constant factors — but those constants come from somewhere real: the engine internals covered throughout this course. Two pieces of code with identical Big-O can have wildly different real-world speed because of them.

```js
function sumMonomorphic(items) {          // every call site sees the SAME shape (Prototypes topic)
  let total = 0;
  for (const item of items) total += item.value; // monomorphic IC — near-free property read
  return total;
}

function sumMegamorphic(items) {           // items mix many different object shapes
  let total = 0;
  for (const item of items) total += item.value; // megamorphic IC — falls back to slow lookup
  return total;
}
```

Both functions are O(n) by the formal definition — same number of operations relative to input size. But `sumMegamorphic`, given an array whose objects don't share a hidden class, pays a real, measurable constant-factor penalty *on every iteration* from losing the inline-cache fast path (Prototype Chain topic) — sometimes several times slower in practice, despite having "the same" complexity on paper.

### Elements kind matters for the same reason

```js
[1, 2, 3].reduce((a, b) => a + b);              // PACKED_SMI_ELEMENTS — flat buffer, fast path
[1, "2", 3].reduce((a, b) => a + b);              // PACKED_ELEMENTS — generic tagged values, slower path
```

Both are O(n) traversals; the Arrays topic's elements-kind ladder means the actual per-element cost differs by a real constant factor depending on what's actually stored, not just how many elements there are.

### The honest takeaway

Big-O tells you how an algorithm **scales** — it remains the right first tool for comparing fundamentally different approaches (O(n²) vs O(n log n) will always lose for large enough `n`, regardless of engine tricks). But *within* the same complexity class, the JIT/hidden-class/elements-kind machinery from earlier topics determines the real constant factor — which is why "this is O(n) so it should be fast" sometimes doesn't hold up under actual profiling, and why consistent object shapes and array contents matter for performance even when they don't change an algorithm's asymptotic classification at all.

## 6. Common Pitfalls

1. **Confusing "fewer lines of code" with "faster"** — a one-line `.includes()` inside a loop can hide an O(n) scan, turning an apparently simple loop into accidental O(n²).
2. **Ignoring space complexity entirely** — an O(n) time solution that also needs O(n²) space might be worse in practice than a slightly slower solution that fits in memory.
3. **Not accounting for recursion's stack space** — assuming a recursive solution is "free" because it looks concise, when it may add O(n) stack depth a loop-based version wouldn't need.
4. **Big-O ≠ actual speed for small `n`** — an O(n²) algorithm can outperform an O(n log n) one for very small inputs, due to lower constant overhead; Big-O only describes behavior as `n` grows large.

## 7. Quick Reference

```
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
nested loops → multiply     sequential loops → add (then simplify)
extra data structure → often trades space for time
recursion depth → counts as space complexity
```