What O-notation is for, and what it hides

A code review comment says "this is O(n squared), rewrite it". The loop runs over a user's enrolled courses. The whole catalogue is a few hundred courses, and a learner is typically enrolled in a handful. The rewrite would save microseconds and cost a reviewer an afternoon.

A second comment, on a different pull request, was never written. That loop calls include? on an array built from every lesson in the catalogue, once per row of a report. Nobody flagged it because the code reads fine.

Complexity analysis earns its place by telling you which of those two matters. It's a decision tool, not a badge.

What the notation claims

O-notation names the shape of a growth curve. It answers one question and refuses every other: when the input gets ten times bigger, what happens to the work?

O(1) says nothing happens. O(n) says the work gets ten times bigger. O(n squared) says it gets a hundred times bigger. O(log n) says it grows by a constant sliver each time you double the input.

That's the whole content of the claim. It's a statement about a limit as n grows without bound, so it's deliberately silent about every finite case you'll ever run.

The three things it throws away

The notation drops constants. An algorithm that does 4000 units of work per element and one that does 3 units are both O(n). On your data, one of them takes a second and the other takes a millisecond.

It drops lower-order terms. n squared + 500n is O(n squared), and for any n below 500 the dropped term does most of the work.

It drops the machine. A sequential scan of an array that fits in L1 cache and a sequential scan of a table on disk are the same curve and different worlds.

So the honest reading of "this is O(n log n)" is: if n keeps growing, this is the shape it will follow. It's a prediction about the future of your data, not a measurement of today.

The question that comes first

Before the curve comes one question: what is n here?

An engineer who says "that sort is O(n log n)" but can't say whether n is 40 or 40 million has produced a true sentence with no information in it. The curve only becomes a decision once it's attached to a number.

This application is a useful example, because its numbers are small. Here are the orders of magnitude, which anyone can see from the catalogue:

At those sizes almost nothing here deserves an asymptotic argument. A linear scan over a few hundred items in Ruby takes a fraction of a millisecond. Saying so out loud helps a team more than pretending the numbers are bigger. It moves attention to the two or three places where n does grow.

Where it stops being numerology

Complexity becomes a senior tool in three situations, and you'll recognize all three.

The first is a curve that hits a wall. Anything quadratic in a user-facing request is fine until it isn't, and the change is abrupt: a page that took 80ms at 300 rows takes 8 seconds at 3000. Linear growth degrades gracefully; quadratic growth falls off a cliff.

The second is a curve you can't see. A query per record inside a loop looks like one line of Ruby. The cost isn't in the Ruby.

The third is a decision between two working implementations. Both are correct, both have shipped, and the only difference is which one wins on your data. That's the threshold question, and it's the heart of this course.

What this course covers

Lesson 2 walks the curves a Rails engineer meets, each attached to a concrete pair. It compares a query per record against one query, an index lookup against a sequential scan, sorting in Ruby against sorting in the database and loading every row against batching.

Lesson 3 is the most common accidental quadratic in Rails code: include? on an array inside a loop. It measures the cost instead of asserting it and shows what Set does to it in current Ruby.

Lesson 4 is space complexity, which juniors ignore and seniors get paged for. The memory curve often hurts before the time curve does.

Lesson 5 is amortized, average and worst case. It covers why a Hash lookup is "O(1)" with caveats, and where the worst case bites in practice.

Lesson 6 is the threshold question. Two implementations have different curves and different constants, and they cross at a point you can compute. It carries the coding challenge.

Lesson 7 is when the analysis is worth doing at all.

Before lesson 2

Open the hottest endpoint you own and find the loops. For each one, write down what n is and what it was a year ago. Skip the curve for now. Write just the number and its direction.