# Time-Space Trade-offs — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/s-tradeoffs

> Trade memory for speed with caching, hashing and precomputation.

## Spending memory to save time

Many speed-ups work by **using more memory**. **Hash sets and maps** turn repeated O(n) searches into O(1) average lookups at the cost of O(n) space. **Memoisation** stores results of subproblems so they are computed once, turning exponential recursion into polynomial time. **Precomputation** builds structures once to answer many queries quickly: a **prefix-sum array** answers any range-sum query in O(1) after O(n) preprocessing, instead of O(n) per query; **sorting** once enables binary searches. **Lookup tables** replace computation with memory reads. The trade-off can go the other way when memory is tight: recomputing values, streaming data instead of loading it, or using in-place algorithms. The right choice depends on constraints: how many queries, how large the data, how much RAM. In interviews, presenting both options ("O(n²) time and O(1) space, or O(n) time and O(n) space with a hash set") shows mature thinking.

## Prefix sums: O(n) preprocessing, O(1) per query

Answering q range-sum queries drops from O(n·q) to O(n + q).

```python
def build_prefix(a):
    prefix = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        prefix[i + 1] = prefix[i] + x      # O(n) time, O(n) space
    return prefix

def range_sum(prefix, left, right):        # inclusive left..right
    return prefix[right + 1] - prefix[left]  # O(1) per query

sales = [120, 80, 150, 90, 200, 60]
p = build_prefix(sales)
range_sum(p, 1, 3)                         # 80 + 150 + 90

# without prefix sums: sum(sales[l:r+1]) per query is O(n) each
```

## Name the trade-off explicitly

Say which resource you are spending and why it is affordable, for example "extra O(n) memory is fine for one million integers, about 8 MB in a packed array".

**Quiz:** Prefix sums answer each range-sum query in O(1). What do they cost?

- [ ] Nothing
- [ ] O(n²) space
- [x] O(n) preprocessing time and O(n) extra space
- [ ] O(log n) per query

*Answer:* O(n) preprocessing time and O(n) extra space. Building the prefix array takes linear time and memory, paid once.