When you see O(log n) on an index lookup, it's not a performance number. It's a growth rate. It tells you what happens to the cost when the dataset doubles, triples, or hits a billion rows.
The constant factors โ CPU speed, cache lines, disk latency โ those matter in practice. But Big O tells you whether your approach survives at scale.
O(1) โ Constant
What it means
The cost doesn't change no matter how big the dataset gets. 10 rows or 10 billion โ same work.
Where you see it
Hash table lookups. Array access by index. Stack push/pop. Getting an element when you already know exactly where it is.
The dream. But "constant" can still be slow if the constant is large โ O(1) with a 5ms disk seek is still 5ms.
O(log n) โ Logarithmic
What it means
Every time the dataset doubles, you do one more step. 1,000 rows โ 10 steps. 1,000,000 rows โ 20 steps. 1,000,000,000 rows โ 30 steps. It barely grows.
Where you see it
B-Tree / B+Tree lookups. Binary search. Any algorithm that halves the problem at each step.
The reason databases work. Going from 1 million to 1 billion rows adds maybe 10 extra comparisons. This is why B+Trees dominate.
O(n) โ Linear
What it means
Double the data, double the work. The cost grows in direct proportion to the input size. You touch every element once.
Where you see it
Full table scans. Counting items. Iterating a list. Any query on a heap without an index. "Check every row."
Acceptable for small datasets. Painful at scale. A full scan of 1 billion rows is 1 billion rows of work โ no shortcut.
O(n log n) โ Linearithmic
What it means
Slightly worse than linear. You touch every element, but at each element you do a log-n operation. Grows gently โ 10ร data means roughly 13ร work.
Where you see it
Sorting (mergesort, heapsort, timsort). Building an index. The cost of organising data so future lookups are O(log n).
The price of order. You pay O(n log n) once at build/sort time so you can pay O(log n) on every future query.
O(nยฒ) โ Quadratic
What it means
Double the data, 4ร the work. Triple it, 9ร the work. Every element compared against every other element. Grows explosively.
Where you see it
Nested loops without indexes. Naive join algorithms. Bubble sort. "For each row, scan every other row."
1,000 rows = 1 million operations. 1 million rows = 1 trillion. This is where bad query plans go to die.
O(2โฟ) โ Exponential
What it means
Every additional element doubles the total work. 20 elements = ~1 million operations. 40 elements = ~1 trillion. Grows so fast it hits physical limits almost immediately.
Where you see it
Brute-force subset problems. Recursive Fibonacci without memoisation. Trying every combination of on/off for n items.
If your algorithm is O(2โฟ), it's not slow โ it's impossible beyond trivial input sizes. Redesign, don't optimise.
The Scale Chart
What these actually look like at real data sizes:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(nยฒ) |
|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 |
| 1,000 | 1 | 10 | 1,000 | 10,000 | 1,000,000 |
| 1,000,000 | 1 | 20 | 1M | 20M | 1T |
| 1,000,000,000 | 1 | 30 | 1B | 30B | 1018 |
Look at the O(log n) column. From 10 to 1 billion, it goes from 3 to 30. That's why B+Trees work at planetary scale.
Amortised Complexity
Some operations are expensive occasionally but cheap on average. A hash table resize is O(n) โ but it only happens every n inserts, so the cost per insert amortises to O(1).
ArrayList/vector append: O(1) amortised (occasional O(n) resize)
Hash table insert: O(1) amortised (occasional O(n) rehash)
Splay tree access: O(log n) amortised (individual ops can be O(n))
Big O gives you the worst case. Amortised gives you the average over many operations. Both matter.
Best, Average, Worst
Big O is usually quoted as the worst case. But some algorithms have very different best and worst cases:
Hash table lookup โ best O(1), worst O(n) if every key collides
Quicksort โ best O(n log n), worst O(nยฒ) on already-sorted input
Binary search โ best O(1) if the middle element matches, worst O(log n)
B-Tree lookup โ always O(log n), best and worst are the same. Predictable.
When Big O Lies
Big O ignores constants and lower-order terms. That's the point โ it shows asymptotic behaviour. But it means:
An O(n) algorithm with tiny constants can beat an O(log n) algorithm with huge constants โ at small n
Cache locality matters more than Big O at small scales โ sequential O(n) can beat random O(log n)
Disk vs memory changes everything โ O(log n) with disk seeks โ O(log n) in L1 cache
Big O says nothing about memory usage โ an O(1) lookup that uses 64 GB of RAM isn't free
Big O tells you what survives at scale. It doesn't tell you what's fastest right now.
Why This Matters for Indexes
Hash table โ O(1) lookup. Doesn't scale badly. Scales perfectly.
B-Tree / B+Tree โ O(log n) lookup. 1 billion rows = 30 steps. That's why databases exist.
Full table scan (heap) โ O(n). 1 billion rows = 1 billion rows of I/O. That's why indexes exist.
Nested loop join (no index) โ O(nยฒ). Two tables of 1M rows = 1 trillion comparisons. That's why query optimisers exist.
Bloom filter โ O(k) where k = number of hash functions. Effectively O(1). Tells you not to bother with the O(log n) lookup.
An index converts an O(n) problem into an O(log n) problem. That's not an optimisation. That's the difference between a system that works and one that doesn't.
Big O is the constraint on the wavefunction of possible implementations. It tells you which approaches survive contact with reality โ and which collapse under their own weight.