# how it grows, not how fast

2023-10-23 · 3 min read · #algorithms

Source: https://jopcmelo.com/writing/how-it-grows-not-how-fast

say you're choosing between two ways to find something in a list: check every item, or [binary search](/writing/guess-my-number). and say checking one item takes 1ms.

with 100 items, checking every one takes 100ms. binary search takes 7. both feel instant. now give them more items:

| items         | check every item | binary search |
| ------------- | ---------------- | ------------- |
| 100           | 100ms            | 7ms           |
| 10,000        | 10 seconds       | 14ms          |
| 1,000,000,000 | 11.6 days        | 30ms          |

**at 100 items they were 93ms apart. at a billion, one takes 30ms and the other almost 12 days.** that's what Big O notation is for. it doesn't say how fast something runs. it says how the time grows as the input does.

## the usual ones

- `O(1)`, constant: the same time however big the input gets, like reading an array by index, or a [hash table](/writing/constant-time-most-of-the-time) lookup.
- `O(log n)`, logarithmic: binary search.
- `O(n)`, linear: checking every item.
- `O(n log n)`: good sorting algorithms, like merge sort, or [quicksort](/writing/pick-a-pivot) on average.
- `O(n²)`, quadratic: comparing every item with every other, like [selection sort](/writing/pick-the-biggest-repeat).
- `O(n!)`, factorial: trying every possible order of the items.

*(sketch: a race over 30 items, one lane per Big O. O(1) and O(log n) finish almost at once, O(n) takes a little longer, O(n log n) is still running when the race starts over, and O(n²) has barely left the start)*

Big O usually describes the worst case, and it drops constants: `O(2n)` is just `O(n)`, because **it's about the shape of the growth, not the exact count**.

## factorial

the classic `O(n!)` is the traveling salesperson: visit every city once and come back home, by the shortest route. the obvious way is to try every order of the cities and keep the shortest one:

| cities | orders to try           |
| ------ | ----------------------- |
| 6      | 720                     |
| 8      | 40,320                  |
| 15     | 1,307,674,368,000       |
| 30     | about 2.65 × 10³²       |

*(sketch: five cities and one route through them. 5 cities: 120 orders. 30 cities: 2.65 × 10³²)*

nobody solves it that way past a handful of cities. the [Held–Karp algorithm](https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm), from 1962, finds the exact shortest route in `O(n² 2ⁿ)`, still exponential but far below `n!`. past that, people settle for a route that's close to the shortest.

## space

the same notation works for memory, and you can often trade one for the other. to check whether two people are friends, you can walk through A's friends every time: `O(n)` time, no extra memory. or keep A's friends in a hash set: an `O(1)` check, paid for with memory for the whole set. **most speedups are memory spent somewhere.**

databases make the same trade with indexes. an index takes up space and [adds overhead](https://www.postgresql.org/docs/current/indexes-intro.html) to every write, so that a lookup can go through a B-tree in `O(log n)` instead of reading the whole table.