Big-O Notation: Measuring How Code Scales

"This function takes 0.3 seconds" tells you almost nothing useful. On what machine? With how much data? Next month, with ten times the users, is it 3 seconds or 30 or 300? Big-O throws away the stopwatch and answers the only question that predicts the future: when the input grows, how does the work grow with it?

Why we count growth, not seconds

Wall-clock time lies. The same code is faster on a newer laptop, slower under load, different in Python versus C. None of that is a property of your algorithm. It's noise from the environment.

So we measure something the hardware can't change: the shape of the cost as the input size n gets large. We count how many fundamental steps the code does as a function of n, then describe that count's growth with Big-O. O(n) means "steps grow in proportion to n." O(n²) means "steps grow like n squared." That description holds on any machine, today and next year.

Big-O is deliberately about the large-input behavior, which is exactly where slowness bites. It's the language teams use to reason about scale before they've written a line, and the thing interviewers want you to speak fluently.

The growth classes you'll actually meet

A handful of shapes cover almost everything you'll write. From flattest (best) to steepest (worst):

• O(1), constant. The work doesn't depend on n at all. Grabbing list[5] takes the same time whether the list has 10 items or 10 million.
• O(log n), logarithmic. Each step throws away half the remaining data. Doubling n adds just one more step. This is binary search, and it's almost as good as constant.
• O(n), linear. Look at each item once. Double the input, double the work. Honest and usually fine.
• O(n log n), linearithmic. The speed limit for general-purpose sorting. A touch slower than linear, dramatically better than quadratic.
• O(n²), quadratic. A loop inside a loop over the same data. Fine for 100 items, painful at 10,000, hopeless at a million.
• O(2ⁿ), exponential. Adding one item doubles the work. The cliff. Brute-forcing every combination lives here, so you avoid it.

Drag the input size in the chart and watch the order assert itself. Down low, the curves tangle and the choice feels like nitpicking. Crank n up and they fan out across orders of magnitude. O(log n) hugs the floor while O(2ⁿ) leaves the building.

The visual lesson: ranking is a large-n phenomenon. The whole point of Big-O is to predict that fan-out before your input gets big enough to feel it.

The two rules: drop constants, drop lower-order terms

Big-O looks at the dominant behavior as n grows, which means two simplifications you apply every time.

Drop the constants. A loop that does three operations per item is O(3n), but we write O(n). The 3 is a fixed multiplier that doesn't change the shape of the curve. Double the input and the work still doubles. Tripling the per-item cost matters in practice, but it doesn't change which growth class you're in, and the class is what decides whether you survive at scale.

Drop the lower-order terms. Code that does n² work plus another n work is O(n² + n), but we write O(n²). For large n, the n² part dwarfs the n part so completely that the smaller term is rounding error. At n = 1,000,000, the square is a trillion and the linear part is a million: the million vanishes.

Both rules say the same thing: keep only the term that dominates as the input gets big, and strip its multiplier. 5n² + 200n + 17 is O(n²), full stop.

Read the cost off the code

Now wire the classes to actual code. The block below builds one function per class and prints its operation count for a given n, so the numbers match the labels.

Look at the columns as n goes 5, 10, 20. The O(1) count never moves. The O(n) count tracks n exactly. The O(n²) count is n × n, and it quadruples every time you double n. That last column is the one that ruins your day at scale, and now you can see it coming from the structure of the code: a loop nested inside another loop over the same data.

Where to go next

Big-O is just a precise way to say "how fast does the work grow," and now you can read it straight off a snippet: count the loops, keep the dominant term, drop the constants. Every data structure from here gets graded in this language: fast lookup, slow insert, and exactly why.

Next: Arrays & Strings, the most-used data structure there is, and a clean tour of which of its operations are O(1) and which are O(n). For a refresher on the loop syntax above, the loops lesson in the Python series has you covered.