Big-O: what "grows faster" actually means

The shape, not the number

An operation count on its own tells you nothing. Two hundred and fifty six operations is fast if the input was a million and slow if it was four. What matters is the relationship between the two, and that is what the notation names.

So read the chart as a shape rather than as heights. O(n) is a straight line: every item costs the same, so twice the items costs twice the work. O(log n) flattens, because each step throws away half of what is left and there are only so many halvings in any number. O(n²) bends upwards, because every new item has to meet every item already there.

What doubling does

The cleanest way to feel a growth rate is to stop looking at the total and start looking at what one doubling costs. Step the animation and read the caption each time.

• Linear: doubling the input doubles the work. Steady, predictable, usually fine.
• Logarithmic: doubling the input adds one operation. Not one per cent. One.
• Quadratic: doubling the input roughly quadruples the work. This is the one that is fine in testing and fails in production.

All six, side by side

The player shows one shape at a time, because each one is measured by actually running it. Comparing them is a different job, so here they are together. This chart is drawn from the formulas rather than measured, which is why it can show all six at once.

Read the bend rather than the height. Flat means the input size does not matter. A line that rises and then levels off is throwing work away every step. A straight line is paying the same for every item. Anything that curves upwards is paying more for each item than for the one before, and that is the only group that eventually becomes unusable.

The same input, four costs

At 200 items the measurements are 8 operations, 200, 1,600 and 19,900. The same data, handed to four algorithms, and the slowest does about 100 times the work of the linear one and 2,488 times the work of the fastest.

That gap is why the notation exists. It is not about being precise about small inputs, where everything is fast and nobody cares. It is about knowing which of these you have written before the input gets large enough to find out the hard way.

How to work it out, for any code

There is a procedure, and it is short. Count what the code does as a function of the input, then throw away everything that stops mattering when the input is large.

1. Decide what n is

Every answer is meaningless without this. The length of an array, the number of nodes in a tree, the number of bits in a number, the number of rows returned. If a function takes two collections, there are two variables and the answer has both in it: O(n + m) for two separate passes, O(n · m) for one nested inside the other.

2. Sequential work adds, nested work multiplies

Two loops one after another cost n + n, which is O(n). A loop inside a loop costs n · n, which is O(n²). Almost every mistake in this topic is confusing those two.

3. Count what the loop body really costs

A loop is only linear if its body is constant. The most common accidental O(n²) in real code is a single visible loop whose body calls something that scans: includes, indexOf, find, a substring search, or a database query. One loop on screen, two loops in the machine.

4. Ask what the loop does to the counter

This is the whole difference between linear and logarithmic. A counter that adds runs n times. A counter that multiplies runs log n times, because repeated doubling reaches n in log₂(n) steps.

for (let i = 0; i < n; i++)      →  O(n)     adds
for (let i = 1; i < n; i *= 2)   →  O(log n) multiplies

5. For recursion, count the calls and the work in each

Multiply how many calls there are by what one call costs outside its recursive calls. Halving the input and doing constant work is O(log n). Halving it and doing linear work at every level is O(n log n), which is merge sort. Making two calls on an input one smaller is O(2ⁿ), which is why naive fibonacci is unusable.

T(n) = T(n/2) + 1      →  O(log n)    binary search
T(n) = 2·T(n/2) + n    →  O(n log n)  merge sort
T(n) = T(n-1) + n      →  O(n²)       selection sort
T(n) = 2·T(n-1) + 1    →  O(2ⁿ)       naive fibonacci

6. Drop constants and lower terms

3n² + 500n + 9000 is O(n²). Not because the other terms are small, but because they stop competing: at n = 10,000 the first term is already six thousand times the second. Keep the term that wins eventually and drop the rest.

The shapes, in order

Every variant above is one of these. Switch between them and watch the vertical scale, which is where the argument actually lives.

• O(1) constant. Array index, hash lookup, arithmetic. The input size changes nothing.
• O(log n) logarithmic. Binary search, balanced tree lookup. Doubling the input adds one step.
• O(n) linear. One pass. Doubling doubles the work.
• O(n log n) linearithmic. Merge sort and heap sort. This is the practical ceiling for putting things in order, and the next lesson shows why nothing that works by comparing pairs can beat it.
• O(n²) quadratic. Nested loops, comparing all pairs. Fine in testing, fatal in production.
• O(2ⁿ) exponential. Every subset, naive recursion over two branches. One more item doubles everything.
• O(n!) factorial. Every ordering. Twenty items is 2.4 quintillion arrangements, so this is only ever a starting point you intend to replace.

The exponential variant is capped at a much smaller input than the others, and that is the honest reason: at 22 items it is already over four million operations, where the linear one has done 22. There is no size at which you can plot them on the same axis and see both.

Why constants are dropped, and when that bites

Big-O ignores constant factors, so an algorithm doing 100 operations per item and one doing a single operation per item are both O(n). That looks like carelessness and is not: the claim is about what eventually dominates, and a constant never changes which shape wins in the end.

In practice it bites at small sizes. A 100n algorithm beats an n²/2 one until about n = 200, so for genuinely small inputs the quadratic can be faster. Most production sort implementations switch to insertion sort, which is quadratic, once a partition is under about sixteen elements, because its constant is tiny.

Worst, average and amortised

The animation measures the worst case, which is what Big-O describes when nobody says otherwise. It is not the only useful question.

Quicksort is O(n²) in the worst case and O(n log n) on average, and it is the average that made it the default sort for decades. Appending to a dynamic array is O(n) on the occasional resize and O(1) amortised, because doubling the capacity makes the expensive step rare enough to spread across the cheap ones. A hash lookup is O(1) expected and O(n) if every key collides.

Space, not just time

The same notation describes memory, and the answer is often different. Merge sort is O(n log n) time and O(n) space because it allocates while merging; heap sort matches its time and uses O(1) space. Recursion costs O(depth) space in stack frames even when it allocates nothing, which is the whole subject of the stack overflow lesson.

What the notation cannot see

Two O(n) algorithms can differ by an order of magnitude in real time, because the model counts operations and the machine charges for memory access. Walking an array and walking a linked list are both linear, and the array can be several times faster because each cache line it fetches brings the next several items with it while the list scatters its nodes.

This is the usual reason a theoretically better algorithm loses a benchmark. Big-O is a model of work, not of hardware, and it is the right model right up until it is not.

Problems

Work them before opening the answers. Reading a solution feels like learning and is not.

for (const x of items) {
  console.log(x)
}

O(n)

for (const x of items) {
  if (others.includes(x)) count++
}

O(n · m), and O(n²) when both lists are the same length.

for (const x of items) {
  if (others.includes(x)) count++
}

const seen = new Set(others)
for (const x of items) {
  if (seen.has(x)) count++
}

for (const x of items) total += x
for (const x of items) largest = Math.max(largest, x)

O(n)

function sort(a) {
  if (a.length <= 1) return a
  const mid = a.length >> 1
  const left = sort(a.slice(0, mid))
  const right = sort(a.slice(mid))
  return merge(left, right)   // merge touches every element once
}

O(n log n)

What gets asked, and what a good answer sounds like

Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.