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. 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 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 on average.
• O(n²), quadratic: comparing every item with every other, like selection sort.
• O(n!), factorial: trying every possible order of the items.

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³²

nobody solves it that way past a handful of cities. the Held–Karp 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 to every write, so that a lookup can go through a B-tree in O(log n) instead of reading the whole table.