Big O, read out loud
Attaching the standard names and notation to patterns you already understand.
Everything in this lesson you already know. The patterns were the hard part and they are behind you. All that remains is the shorthand the rest of the world writes them in, so that when you see it in the wild you can read it comfortably rather than flinching.
The shorthand is a capital letter O with something in brackets after it. O(n) is said out loud as "oh of n" or "order n", and it means this grows in proportion to n. That really is all it is claiming.
The other brackets you are about to see hold three more scraps of shorthand, so here is what each of them is short for, before the table rather than after it.
O(1)has a 1 in it because the cost is some fixed number of steps. You may reasonably ask why it is not a 0, since the cost does not grow: the answer is that the cost is not nothing, it is just not affected by n. And since the notation throws away multipliers anyway, as you will see below, we may as well write the simplest fixed number there is.O(log n)useslogas the usual short spelling of logarithm. Read it as "the number of halvings", which is exactly the count you worked out in the last lesson.O(n^2)uses the^2to mean squared, that is, n multiplied by itself.n^3would be n times n times n, and so on.
| The pattern, in words | Written | Usually called | Something that behaves this way |
|---|---|---|---|
| Does not grow | O(1) | constant time | Taking the top plate off a stack. |
| Barely grows: one more step per doubling | O(log n) | logarithmic time | The guessing game. Searching a sorted collection. |
| Grows in step with the data | O(n) | linear time | Checking every name in a list. |
| Grows a little faster than in step, the fifth pattern | O(n log n) | linearithmic time, that is, linear times logarithmic | Good sorting methods: n items, each handled once per halving. |
| Grows with the square | O(n^2) | quadratic time | Comparing every item with every other item. |
The left-hand column of that table holds the five patterns in the words used for them earlier, and they are the words the five lines were labelled with on the chart two lessons back. The picture has not changed and neither have the patterns. Only the writing is shorter now, so if you want the shapes back, look at that chart again with the middle column of this table beside it.
The last one is often printed with a small raised 2 instead of the caret, which means the same thing. You will also hear people use the names as adjectives: "the lookup is constant time", "that loop is linear", "it degrades to quadratic". They are describing the columns of that table and nothing more.
What the notation deliberately ignores
Big O throws away two things on purpose, and knowing what it discards is most of what it takes to read it correctly.
First, it ignores fixed multipliers. Something taking 3 steps per item and something taking 1 step per item are both O(n), even though one is three times the work. Second, it ignores everything except the fastest-growing part. Consider a routine that takes 3n plus 50 steps, that is, fifty steps of setting up plus three steps per item:
| n | 3n | plus 50 | Total | Share that is the fixed 50 |
|---|---|---|---|---|
| 10 | 30 | 50 | 80 | 63% |
| 100 | 300 | 50 | 350 | 14% |
| 10,000 | 30,000 | 50 | 30,050 | 0.2% |
| 1,000,000 | 3,000,000 | 50 | 3,000,050 | 0.002% |
By the bottom row the 50 has vanished into the rounding, and the whole thing is behaving like 3n. And 3n has the same character as n: double the data and both double. So we write O(n) and move on.
This also settles a loose end from three lessons ago. A step was defined vaguely there, and you were told the vagueness would turn out not to matter. Here is why it does not. If your idea of a step is three times bigger than mine, then every count you make is three times smaller than mine, and all that differs between us is a fixed multiplier. The notation throws those away, so we end up writing the same thing.
Method A takes 1000 steps per item. Method B takes n steps per item, so n times n in total. Which is better?
It depends on the size of your data. Below 1,000 items B is faster, and at 1,000 they are equal. Above that A wins and the gap widens without limit: at a million items A takes a billion steps and B takes a million million. Big O calls A better because it describes the long run, which is exactly why you should check your real data size before trusting it.