Big-O, measured

Big-O is usually taught as a table to memorise, and a table is the least useful form of it. What it actually gives you is an answer to one question: when this gets bigger, what happens?

And the reason that question matters is the thing the table hides — a wrong choice is invisible at the size you test with.

#The same program, three sizes

Two ways to ask "have I seen this before": a List and a HashSet. Both correct. Both obvious. Here is contains() called n times as n grows:

###          n      List ms   HashSet ms
###       1000          3.0          0.2
###      10000         35.6          0.4
###     100000       3454.4          1.8

Read the columns, not the rows.

n went up 100×. The List time went up 1,150×. The HashSet time went up 9×.

That is what Big-O describes. List.contains scans until it finds the element, so one call is O(n) and n calls are O(n²). HashSet.contains computes a hash and looks in one bucket — one call is O(1), so n calls are O(n).

Now the row that explains why this ships:

###       1000          3.0          0.2

Three milliseconds against two tenths. Nobody notices that. It passes review, it passes the test suite with its twenty rows of fixture data, and it is fifteen times slower in a way no one can feel. At a hundred thousand it is nineteen hundred times slower and the endpoint takes three and a half seconds.

#The shapes worth recognising

The middle column is the useful one. "Doubling n quadruples the time" is a sentence you can apply to your own code in your head; "quadratic" is a word.

And the practical boundary: O(n²) is fine until it is not, and the cliff is around a few tens of thousands. A nested loop over a hundred items is ten thousand operations and instant. Over a hundred thousand items it is ten billion, and you will be waiting.

#What the notation deliberately throws away

Big-O keeps the growth and discards everything else, which is what makes it portable across machines and languages — and what makes it misleading when misused.

• Constants are dropped. O(n) and O(100n) are both O(n). So an O(n) algorithm can genuinely be slower than an O(n²) one at the sizes you care about, and for small n it often is.
• Lower-order terms are dropped. n² + n is O(n²).
• It describes the worst case unless stated. HashMap.get is O(1) on average and O(log n) in a bucket that has degenerated into a tree — which is a real behaviour of Java's implementation and is covered by the collections course.

#Amortised, which is why ArrayList is allowed to say O(1)

ArrayList.add is O(1), and occasionally it copies the entire backing array to a bigger one, which is plainly O(n). Both are true.

The resolution is amortised cost: the expensive copies are rare enough, and grow far enough apart, that the average over many adds is constant. Because the array doubles, adding n elements does at most about 2n copies in total — so the cost per add, spread out, is a constant.

This is worth understanding rather than accepting, because it is the same argument behind HashMap resizing, behind StringBuilder, and behind every buffer that doubles. And it has a real edge: amortised O(1) is not O(1) for any individual call. In a latency-sensitive path, the one add that triggers a copy of a million elements is a spike, and that is why new ArrayList<>(expectedSize) exists.

#Where this actually lands: which collection you are choosing

The reason a Java engineer learns this is not interviews. It is that every collection in the standard library is a different set of these trade-offs, and choosing is a daily decision:

If a List is being searched with contains inside a loop, that is the first table row and the measurement at the top of this lesson. It is the single most common accidental O(n²) in ordinary business code, and it is one line to fix.