Big O notation · part 8 of 8
The big O cheat sheet
On this page
Here's the whole series summarised, for when you need a refresher.
The shapes
| Notation | Name | What it means | You see it when |
|---|---|---|---|
O(1) |
constant | doesn't grow at all | a Map or Set lookup by key |
O(log n) |
logarithmic | how many times you halve n to reach 1 |
binary search in a sorted list |
O(n) |
linear | grows in step with the input | one scan through a list |
O(n log n) |
linearithmic | a scan, repeated for each level of halving | a good sort (JS .sort()) |
O(n²) |
quadratic | a loop inside a loop over the same data | comparing every pair |
O(2ⁿ) |
exponential | doubles with every extra item | trying every on/off combination |
O(n!) |
factorial | multiplies by every count down to 1 | trying every possible ordering |
The recipe
- Find what repeats with the input. Loops over the data, and the disguised ones:
.includes(),.indexOf(), a nested.find()are loops in a method's clothing. - Nested loops multiply. Steps in sequence add.
- Keep the fastest-growing term and bin the constants.
What survives
- O(log n) / O(1): free. Anything.
- O(n) / O(n log n): millions, comfortably.
- O(n²): fine in the low thousands, dead at a million.
- O(2ⁿ) / O(n!): a couple of dozen, and that's your lot.
Data-structure costs
| Structure | Find by key/index | Insert | Search for a value |
|---|---|---|---|
| Array (by index) | O(1) | O(1) at the end | O(n) |
| Hash map / Set | O(1) average | O(1) average | O(1) average |
| Balanced tree | O(log n) | O(log n) | O(log n) |
| Heap | O(1) peek | O(log n) | O(n) |
| Linked list | O(n) | O(1) at a known spot | O(n) |