How I wish I was taught big O notation
You'll hear "O(n squared) is bad", but do you know why? If all goes to plan, by the end of this series you will. If it goes really well, you'll also be able to look at a function and work out its big O yourself.
We'll need something to count, so we're returning to our ice cream van: Sundae Service. As the season goes on we get more flavours, more customers, more orders. Some of the code copes fine when things get busy, but some of it breaks. Big O is the tool for telling which is which before the bank holiday rush!
The short version
Here's the end game. You don't need to understand everything yet as I've split each into its own module below. Treat this as a map, and the page to come back to when you want a quick reminder.
| 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 core idea is that: n is the size of the input, and big O is how the work grows as n grows. Not how fast it runs, but how it scales.
Let's get it.