It is about growth, not speed
Big-O answers one question: when the input gets bigger, what happens to the work? It says nothing about milliseconds. An O(n²) algorithm can beat an O(n log n) one for the sizes you actually have, and often does.
The reason it is worth learning anyway is that growth is the part you cannot fix later. A constant factor is a faster machine or a tighter loop; a bad growth rate is a program that works in testing and dies in production.
The rates you will meet
The jump that matters most is between O(n log n) and O(n²), because that is the line between "handles the whole dataset" and "was fine on the test fixture". A million items at n log n is twenty million operations; at n² it is a trillion.
And O(log n) barely grows at all: a thousand items cost ten probes, a million cost twenty. That is why binary search and balanced trees are everywhere.
| Growth | Name | n = 1000 | n = 1 000 000 |
|---|---|---|---|
| O(1) | constant | 1 | 1 |
| O(log n) | logarithmic | 10 | 20 |
| O(n) | linear | 1 000 | 1 000 000 |
| O(n log n) | linearithmic | 10 000 | 20 000 000 |
| O(n²) | quadratic | 1 000 000 | 10¹² — a week |
| O(2ⁿ) | exponential | 10³⁰¹ — never | never |
The rules for writing it
Rule four is the one people get wrong in interviews and in production: two loops with different inputs multiply their own sizes. Name them, and the analysis stops being guesswork.
/* 1. Drop the constants: 3n + 50 is O(n) */
for (const x of items) { a(x); b(x); c(x); } // O(n), not O(3n)
/* 2. Keep only the fastest-growing term: n² + n + 1000 is O(n²) */
for (const x of items) for (const y of items) pair(x, y);
for (const x of items) single(x); // O(n² + n) = O(n²)
/* 3. Sequential is addition, nested is multiplication */
sort(items); // O(n log n)
for (const x of items) … // + O(n) → O(n log n)
for (const x of a) for (const y of b) … // O(a × b), NOT O(n²) unless they are the same n
/* 4. A different input is a different n */
for (const word of words) for (const ch of word) … // O(total characters), not O(words²)Best, average and worst
Quicksort is the default sort almost everywhere despite an O(n²) worst case, because the average is excellent and its constant factor is small. Insertion sort is O(n²) and still the right choice below about a dozen items — which is why every real sort switches to it at the bottom.
| Best | Average | Worst | |
|---|---|---|---|
| Quicksort | n log n | n log n | n² — on already-sorted input, with a naive pivot |
| Hash lookup | 1 | 1 | n — when every key collides |
| Insertion sort | n | n² | n² |
| Binary search | 1 | log n | log n |
What the notation throws away
So the honest summary is: use Big-O to choose the approach, and a profiler to choose the implementation. The performance course is about the second half.
- Constants. An O(n) pass that touches the disk loses to an O(n log n) one in memory, every time.
- Memory locality. Walking an array beats walking a linked list of the same length, because the array is one cache line after another. The notation cannot see this, and it is often a factor of ten.
- Space. Merge sort and quicksort are both O(n log n) in time; one needs O(n) extra memory and the other O(log n). On a big array that decides it.
- The actual n. Below a few hundred items, almost nothing in this course matters. Above a few million, almost all of it does.