Nobody at the whiteboard wants a proof — they want you to read n from the constraints and refuse to write a doomed loop. This chapter turns complexity from an exam topic into a weapon: a budget, a table, and a thirty-second elimination ritual.
In school, Big-O is something you prove. In an interview, it's something you use — before writing a single line — to kill the approaches that cannot possibly finish in time. The constraints block at the bottom of every problem is not legal boilerplate; it's the interviewer telling you, in a coded whisper, which of the twenty patterns are still in the running.
This is the last chapter of Part I's meta-game. Chapter 2 gave you the six-step loop; this chapter arms step three ("brute force out loud, name its cost") and step four ("find the pattern") with actual numbers. After this, every pattern chapter can say things like "n is 10⁵, so the nested loop is illegal" and you'll nod instead of squinting.
Here's the reframe that makes this chapter short: in the room, you will almost never be asked to derive a bound with limits and constants. You'll be asked, implicitly and constantly, to not choose a doomed approach. Complexity analysis in anger is a veto power: it strikes candidates off the list so the survivors get your attention.
That flips the usual workflow. Most people read the story, invent an approach, and only then wonder if it's fast enough. The pattern-recognition move is the reverse: read the constraints first, compute what's affordable, and let that decide which patterns are even allowed to bid. Half your search space disappears before you've thought about the actual problem — which is the entire point of Chapter 1's thesis: spend your in-room brainpower on the disguise, not the mechanism.
Three facts make the veto cheap to run: computers do a roughly knowable number of operations per second, growth rates separate brutally fast, and problem-setters choose their constraint numbers on purpose. The next three sections give you each fact as a tool.
The whole system runs on one rule of thumb: about 10⁸ simple operations per second. Array reads, additions, comparisons — the cheap stuff a tight compiled loop does. Online judges typically give you one or two seconds, so 10⁸ is your budget; an approach that needs 10¹⁰ operations isn't "a bit slow", it's a hundred seconds of silence followed by a timeout.
The rule is deliberately fuzzy — and that's fine, because growth rates are so violently different that a factor of ten in the budget almost never changes the verdict. Watch what happens at n = 10⁵:
Notice there's no borderline case in that list. That's typical: problem-setters pick n so the intended complexity fits comfortably and the next class up busts by a factor of 100+. The budget question almost always has a crisp answer.
You've seen the growth-rate chart in every textbook. Here it is with the one thing textbooks leave out: the budget line. Both axes are logarithmic — each gridline is a factor of ten — and the dashed ochre line is your 10⁸ budget. Drag n, or press race and watch the classes die in order: O(2ⁿ) before n hits 30, O(n²) at n = 10⁴, O(n log n) in the millions. The green survivors at the bottom are why "sort it" and "hash it" are the reflexes of Chapters 4–9.
Two readings worth taking away. First, the exponential curve is barely on the chart — it exits the top before n reaches 60, which is why exponential patterns (backtracking, Chapter 18) are only ever sanctioned for tiny n. Second, look how close O(n) and O(n log n) run: the log factor costs about 17× at n = 10⁵. Rule of thumb: log factors are almost free; polynomial degrees are life and death.
Because problem-setters choose n to make the intended solution comfortable, the constraint line runs backwards: from n, you can read off the complexity they expect, and from the complexity, the patterns that produce it. This is the table to burn into memory — it's arguably the highest-value half page in the book:
The table cuts both ways. n ≤ 100 with a problem that smells like it wants something clever? The constraint says the interviewer will accept O(n²) — or even O(n³) — so state the simple version and ship it. Gold-plating a solution the budget didn't ask for costs time and buys nothing.
Time to make the table a reflex. The widget deals you real constraint lines; your job is to name the worst complexity that still fits the 10⁸ budget — worst, because that's the ceiling the problem-setter designed for, and knowing the ceiling keeps the widest set of patterns available. The widget actually computes the operation counts, so the verdicts are arithmetic, not vibes.
Notice the drill's third verdict, the yellow triangle: picking a class that fits but underestimates the ceiling isn't wrong, but it narrows your options for no reason — like folding a winning hand. If the budget allows O(n²) and you can only think of the O(n²) answer, that's not a failure. That's Tuesday.
One word trips people up in complexity conversations: amortized. You've relied on it forever — every list.append, every ArrayBuffer += — because dynamic arrays double their capacity when full. Most pushes cost one write; occasionally a push lands on a full array and pays to copy everything into a bigger one. Worst case for a single push: O(n). And yet append is honestly called O(1). How?
Because the expensive pushes are exponentially rare. Doubling from capacity 4 means copies happen at sizes 4, 8, 16, 32… — the total copy work for n pushes is n/2 + n/4 + … < n, a geometric series. Spread ("amortized") over all n pushes, total cost stays under 3 writes per push, forever. The widget below runs the real machine: watch the spikes get taller and rarer, while the running average flatlines.
Time gets the drama, but space is scored with the same budget logic — 10⁵ integers is nothing, 10⁵ × 10⁵ booleans is 10 GB of "wait, no". Three space facts pay rent in interviews:
Finally, the flip side of the elimination game: constraints take options away, but one word in a problem statement gives options. If the input is already sorted — or sortable without breaking anything — a whole discount catalogue opens: binary search (ch. 9) finds anything in O(log n), two pointers (ch. 5) replace nested scans, duplicates become neighbors, and merging is linear. Half the patterns in Part II are cheap precisely because sortedness prepaid the hard part.
Here's the whole chapter as a habit. When a problem appears, your eyes go to the constraints before the story — the way a chess player counts material before admiring the position. Thirty seconds of arithmetic buys you a pattern shortlist, a spoken cost estimate for your brute force, and the quiet confidence of someone who knows the nested loop is illegal before writing it. Chapter 23's decision tree starts exactly here: constraint size is one of its first questions.
And remember the deal from Chapter 2: the brute force still gets said out loud, always — "brute force is all pairs, n², which at 10⁵ is 10¹⁰ — over budget, so I need n log n or better" is one sentence that scores on three dials. The budget doesn't replace the brute force; it prices it.
The pattern, as a whiteboard skeleton:
One problem, priced three ways. Contains Duplicate Easy: does any value appear at least twice? The brute force compares every pair — at n = 10⁴ that's 49,995,000 comparisons in the worst case, and at n = 10⁵ it's five billion: dead on arrival. Sorting first makes duplicates neighbors (section 7's gift, bought at retail), so one adjacent-scan suffices: about 1.2×10⁵ comparisons at n = 10⁴, four hundred times cheaper. And the hash set — Chapter 4's superpower, previewed — asks "have I seen this?" in O(1): 10,000 lookups, done.
The counts in the comments are worst-case measurements at n = 10⁴ with no duplicate present (the most expensive case — early exit never fires). Read the three functions as three rungs of the elimination ladder: what the constraints allow decides which rung you're expected to stand on.