Big-O notation & analysis

Time the same code on a new laptop and on a five-year-old one, and you get two different answers. Seconds measure the machine as much as the code.

So instead you count steps: the simple operations the code performs, such as a comparison, an addition or reading one value. You count them as a function of the input's size, called n. How the count grows with n is the code's time complexity.

The exact count rarely matters. What matters is the shape of the growth:

• does doubling the input double the work,
• multiply it by four,
• or barely change it?

That shape decides whether the code still runs in reasonable time when n reaches a million.

Say a function takes 3n² + 5n + 2 steps. At n = 1,000 that is 3,000,000 + 5,000 + 2: the n² term is 99.8% of the total, and its share keeps rising as n grows. The constant 3 doesn't change the shape either: a machine twice as fast changes the constant, not the growth.

Big-O notation keeps just that shape. Drop the smaller terms, drop the constant factor, and 3n² + 5n + 2 becomes O(n²), read "order n squared".

The precise version: a step count f(n) is O(g(n)) when there is a constant c and a size n₀ such that f(n) ≤ c × g(n) for every n ≥ n₀. In words, past some size, f never grows faster than a constant times g.

That makes Big-O an upper bound, so a function that takes n steps is also, technically, O(n²). Nobody says that in practice: when people give a Big-O, they mean the tightest one they can, the shape the count really has. Textbooks write that tight version as Θ (theta).

You can usually read the order straight off the code. A single loop over the input does a fixed amount of work per item, so the steps grow in step with n: linear time, O(n).

Put a loop inside a loop and the counts multiply. Comparing every item with every later item makes (n − 1) + (n − 2) + … + 1 = n(n − 1) ÷ 2 comparisons. Drop the constant and the smaller term, and that is quadratic time, O(n²): ten times the items, a hundred times the work.

The third shape is the most valuable one. If each step rules out half of what is left, the way you might open a dictionary in the middle and keep only the half with your word, then n items take only as many steps as you can halve n before reaching 1. That is log₂ n, logarithmic time, O(log n). A million items need just 20 halvings. (The base of the logarithm only changes a constant factor, so Big-O leaves it out.)

Two more rules cover most code:

• Loops one after another add: O(n) + O(n) is still O(n).
• Work that doesn't depend on n at all, like reading one known value, is constant time, O(1).

At small sizes every order looks fine. The table shows what happens as n grows:

Suppose a computer does about a billion simple steps a second (a rough figure; real costs vary a lot). At a million items, an O(n log n) solution finishes in about 0.02 seconds. An O(n²) one takes about 17 minutes. No faster machine closes a gap that size, which is why the order matters more than any constant.

Some orders grow even faster. O(2ⁿ), which doubles with every extra item, already passes 10³⁰ at n = 100. Code with that shape only works on tiny inputs.

Searching an unsorted list for a value can take one step, if the first item is the one you want, or n steps, if it is last or missing. Same code, different inputs, different counts.

A common mix-up is that "Big-O means the worst case". It doesn't: Big-O describes how a step count grows, and you can state it for the best, the worst or the average case. When nobody says which case they mean, as in most interviews, they mean the worst case, because it is a promise that holds for every input.

Space complexity applies the same idea to memory: how the extra memory the code needs, beyond its input, grows with n.

Adding up a list needs one running total whatever the length: O(1) extra memory. Making a copy of the list to work on needs room for n more items: O(n). Time and space often trade against each other, and the next pages show many examples where using O(n) memory turns an O(n²) solution into an O(n) one.

Space & amortized analysis goes further: which memory counts, and how to price an operation that is usually cheap but occasionally expensive.