01You Can't Try Everything

Two computers get the same job: put ten million records into order.

The fast computer is a thousand times quicker, and the best programmer alive hand-writes its machine code.
The slow computer is ordinary. Average programmer. Careless compiler.

The slow computer finishes in nineteen minutes.
The fast computer takes five and a half hours.

A thousand times the hardware, and it lost by seventeen times. I stacked that deck as hard as I could and it was not close.

Here is why, and it is the whole page. The fast computer used a method that compares every pair — fifty trillion comparisons, and it had to do all of them. The slow computer used a method that never looks at most pairs at all. Being quick could not save the first one, because it was still trying everything.

That is the thing worth learning. You cannot try everything — and once you can see how fast "everything" grows, you can work out what any method must cost before you write a line of it. Your first job below is to rescue the fast computer: drag its speed as high as you like. You will not manage it. Why you can't is what the rest of this page is for.

01The bet you cannot win

When something is too slow, almost everyone reaches for a faster machine first. More cores. A faster language. A bigger instance. That reflex is not stupid — it works constantly, and it is often exactly the right call. But it is a bet, and the bet is this: that a faster machine can outrun a better method. I want to find the edge of that bet, so I am going to rig the fight in the machine's favour as hard as I know how. The machine still loses, by seventeen times. Here is the deck I stacked, and watch me stack it.

The job is to put ten million records into order (n = 10,000,000), and I am choosing every number below, so watch me choose them.

Machine FAST performs ten billion elementary operations a second (10¹⁰), and the best programmer alive has hand-written its machine code. FAST runs the pairs method — compare items pairwise and slide them into place — which costs about 2n² operations. For a thousand records that is two million operations (2 × 1,000² = 2×10⁶).
Machine SLOW performs ten million operations a second (10⁷ — one thousandth of FAST). An average programmer wrote its code in a high-level language, on a compiler that leaves performance lying around. SLOW runs the halving method — split the pile in two, order each half, then merge the ordered halves back together — which costs about 50 n log₂ n operations. For the same thousand records that is half a million (50 × 1,000 × log₂ of 1,000 ≈ 5×10⁵), because log₂ of 1,000 is about 10.

Now look at the two constants I just handed out, because one of them is a gift to FAST.
The halving method pays 50 operations per unit of work.
The pairs method pays 2.
The better method carries twenty-five times more overhead on every unit of work it does, and that overhead is what a better shape costs to run. I gave FAST that advantage too.

Now count the work each one has to do.

The fast computer must compare every pair. Ten million records make fifty trillion pairs (n(n−1)/2 with n = 10 million, ≈ 5×10¹³), and the pairs method spends about four operations on each pair — two hundred trillion operations (2n² = 2 × (10⁷)² = 2×10¹⁴). The fast computer gets through ten billion operations a second, so it needs five and a half hours (2×10¹⁴ ÷ 10¹⁰ = 20,000 seconds).

The slow computer splits the pile in half, again and again. Ten million items only survive twenty-three halvings (log₂ of 10 million ≈ 23.25) — so the slow computer does twelve billion operations (50 × 10⁷ × 23.25 ≈ 1.16×10¹⁰) instead of two hundred trillion. It only manages ten million operations a second, a thousandth of the speed, and it still finishes in nineteen minutes (1,163 seconds).

Two hundred trillion operations against twelve billion. That gap is seventeen thousand to one (2×10¹⁴ ÷ 1.16×10¹⁰ ≈ 17,200). The fast computer's thousand-fold speed pays off a thousand of that gap, and seventeen times is the part it cannot pay — which is exactly where the seventeen comes from. The better method wins by seventeen while doing everything else worse.

So rescue the fast computer. The figure below hands you both of FAST's dials: how many times faster FAST runs, and how much cheaper each of FAST's operations is. Push them anywhere you like, up to a billion-fold. Your target is a setting where the pairs method wins and keeps winning as the pile grows. Commit to a yes or a no before you touch anything. Is there such a setting?

There is no such setting, and failing to find one is the lesson. Every setting you tried moved the crossing point. Not one of them removed it. A billion-fold faster machine pushes the crossing out to 996 billion records (the n that solves n = 25×10⁹ × log₂ n), which sounds like winning. Look at what it actually is: a finite number sitting on the same axis your data grows along. Nothing about your data has promised to stay underneath it. That is the bet from the top of this section, and you have just lost it with a billion-fold machine in your hand.

Sliding a curve down cannot bend it, and two curves with different bends meet. That sentence is the entire crossover, and here is the line of algebra under it. The time a program takes is how many steps it does multiplied by what one step costs (time = step count × cost per step). Two factors, and only two. Everything you can buy is a discount on cost per step — a faster clock, more cores, a better compiler, hand-written assembly, dropping from Python to C. A discount on cost per step is a multiplier: it divides the whole curve by a number, so the curve slides straight down and keeps its shape exactly. Step count is the shape itself, how the count grows as n grows, and no amount of dividing changes a shape. So the two curves still meet, exactly where they were always going to meet.

You already own this algebra, and you probably used it this morning. You need to get somewhere. Walking costs nothing to begin and then a steady 12 minutes a kilometre: cost = c·x, with c = 12. The bus costs you a 10-minute wait at the stop before you move at all, and then only 3 minutes a kilometre: cost = a + b·x, with a = 10 and b = 3. Short trip, you walk, because the wait would be most of the journey. Long trip, you take the bus, because 3 minutes a kilometre beats 12 and every extra kilometre multiplies that difference. The two are exactly equal at 1.11 km (x = a/(c − b) = 10/(12 − 3) = 1.11). Below 1.11 km, walk. Above it, wait for the bus.

That is not an analogy for the crossover. It is the crossover with the letters renamed, and I would rather you check that than take it from me. The bus's 10-minute wait is the halving method's overhead — the 50 it pays per unit of work, against the pairs method's 2. The bus's 3 minutes a kilometre against walking's 12 is the halving method's better growth against the pairs method's worse one. And notice the thing neither story lets you skip: you cannot say which option is better until somebody tells you the distance — or the n. Drag the distance in the figure, then throw the relabel switch, and watch the identical two lines become the sorting problem with nothing moved.

Growth rates tell you a crossover exists. They cannot tell you where it is. Where is built entirely out of the constants that growth rates throw away — the 12 and the 10 and the 3, or on a real machine cache behaviour, branch prediction, how big your records are, which compiler you happened to have that afternoon. So the honest answer to "faster above what n?" is always measured, never derived. In the next figure the two constants are hidden from you on purpose, and there is no way to reason them out. You run both implementations at a few sizes and read the crossing off your own measurements, the way you would have to at work.

So a faster machine buys you a constant, and constants are real money. A 3× win takes a $900 monthly bill down to $300, and I have watched a team save more with a compiler flag than with a rewrite. What a machine cannot buy is a different shape. The shape is what wins in the end, and it wins by amounts with no ceiling. Which leaves the obvious question, and it is where the rest of the page lives: where does a shape come from?

02Count the answers before you write a line

Start with the crudest method there is, because it is the one you would reach for under pressure and it always works. List every candidate answer, check each one, keep the best. Nothing about it is clever and nothing about it is wrong. The only question is whether you can afford it — and you can settle that with one number: how many candidates are there? Read that number off the problem statement, which you can do before you write a line of code, then divide by how many you can check per second. Twenty delivery depots gives you 2.4 quintillion candidate routes (20! = 2,432,902,008,176,640,000), which is 77 years at a billion checks a second. That verdict cost you no code at all.

Two shapes cover an enormous amount of what you will meet, and each one is a one-line derivation.

Suppose the answer is an order of n things — a route through n depots, a schedule of n jobs, a sorted list. You pick any of the n for first place, any of the remaining n−1 for second, and so on down. That is n! candidates: fifteen depots is 1.3 trillion orders (15! = 1,307,674,368,000), twenty depots is 2.4 quintillion (20! = 2,432,902,008,176,640,000).
Now suppose the answer is a subset of n things — which features go in the release, which items go in the van, which servers stay up. Each item is independently in or out, so there are 2ⁿ candidates: forty features is 1.1 trillion subsets (2⁴⁰ = 1,099,511,627,776), sixty features is 1.15 quintillion (2⁶⁰ = 1,152,921,504,606,846,976).

Between them, those two counts price almost every brute force you will ever consider.

Then watch what the factorial actually does, at a billion candidates checked per second.

Ten things in an order: 3.6 million candidates (10! = 3,628,800) — four thousandths of a second, and a laptop eats it.
Twenty things: 2.4 quintillion candidates (20! = 2,432,902,008,176,640,000) — 77 years.
Twenty-five things: 1.6×10²⁵ candidates (25! ≈ 1.551×10²⁵) — 492 million years.

Five more items cost a factor of six million (25! ÷ 20! = 6,375,600), and you did not write a line of code to earn it. Watch it arrive, one n at a time, and note where the column stops fitting on your screen.

Money does not touch a factorial, and that is the striking part. Buy a thousand machines and run them in parallel, so you check a trillion candidates a second instead of a billion. Twenty things falls from 77 years to 28 days (2.43×10¹⁸ ÷ 10¹² ≈ 2.43×10⁶ seconds) — a genuine improvement, and still not a product. Twenty-five things falls from 492 million years to 491,000 years. And the tame one, the merely exponential 2ⁿ, gives ground just as grudgingly: sixty features costs 36 years at a billion a second (2⁶⁰ ÷ 10⁹ ≈ 1.15×10⁹ seconds), the thousand machines drop that to 13 days, and seventy features puts it straight back to 37 years (2⁷⁰ ÷ 10¹² ≈ 1.18×10⁹ seconds). Ten more features ate the entire data centre. The factorial column walking off the screen is not a flourish; it is the reason this field exists at all.

Every fast algorithm is a way of not enumerating. That is the sentence worth keeping, and it names a mechanism rather than striking an attitude. A sorting routine never builds a candidate ordering and never rejects one. It asks a sequence of yes-or-no questions about pairs and lets the answers narrow the field, and it finishes having never held a single one of those n! orderings as an object — sort a mere twenty items and that is 2.4 quintillion orderings it never made (20! = 2,432,902,008,176,640,000). A route-finder does not price routes either. It grows one frontier outward and discards every path that reaches a place more expensively than a path it already has. So when you meet a new algorithm, ask it the first useful question there is: which enumeration is it dodging, and by what trick?

Which makes the counting habit worth practising, because it is what you do on day one of a problem nobody has labelled for you. Read the problem. Decide whether the answer is an order of n things, a subset of them, or a pair out of them — and a pair is the cheap one, only 12.5 million candidates for five thousand sensor readings (n(n−1)/2 with n = 5,000, ≈ 1.25×10⁷), which is twelve thousandths of a second. Get the count. Divide by what you can check per second. The figure deals you problems in plain words and no labels. You classify them, and it prices your verdict against the n you say you actually have.

One honest limit before we move on, because this section is easy to over-read. Counting the candidates tells you that brute force is off the table. It does not tell you that anything better exists. For a handful of famous problems nobody has found a method that avoids the enumeration, and nobody has proved that none exists either. That unresolved gap gets a page of its own further on. Here the count is doing a narrower and more immediate job. It prices the method you were about to reach for, so you know what you are shopping for instead of discovering it in production.

03What is a step, and what is n?

I have been saying "operations" and "steps" as though those words were obvious. They are not, and every number on this page rests on them. So both need pinning down: what counts as one step, and what n counts. Get either wrong and the arithmetic still runs perfectly — it just stops meaning anything, which is worse than failing. Get the first one wrong and you can prove sorting is free. Get the second one wrong and a 3,000-year algorithm passes for a linear one, which is the mistake a real person makes in a real meeting.

A step is one operation a machine really performs in a fixed amount of time, no matter how large your data is. Add two numbers. Compare two numbers. Load a word from memory, store one, take a branch. Why be so fussy about a list that dull? Because of what happens if you are not. Suppose we allow the model one extra instruction, sort(A), that puts an array in order in a single step. Every sorting algorithm now costs one step — ten million records, one step, and the five and a half hours from section 1 have evaporated. Sorting is solved, on paper, and the model is worthless. So a cost model has to be chosen, and chosen so that it cannot cheat. The whole discipline is one question, asked of every operation you want to call free: does a real machine do this in constant time?

The sharpest version of that trap catches people who would never dream of writing sort(A). Calling a function is constant work — push the arguments, jump. Running its body is not. So a line reading best = min(candidates) is one line and it is emphatically not one step: a thousand candidates is a thousand comparisons (n steps, with n = 1,000). If you are counting lines, you have quietly reinvented the sorting instruction with a costume on. Sort the operations below into legal and illegal, and the rule stops being a principle and becomes a habit.

Now the other half, and this is where fake results genuinely come from. n has to be declared before a running time means anything, and the right choice is not always the obvious one.

For sorting, n is the number of items, because that is what you were handed.
For multiplying two integers, n is the number of bits, because a bigger number is a longer input rather than a bigger collection.
For a graph you need two numbers, vertices and edges, because neither one bounds the other.

That last one is not fussiness. The same 1,000 vertices can carry as few as 999 edges or as many as 499,500 (n(n−1)/2 with n = 1,000) — a five-hundred-fold difference in the work, with n = 1,000 either way. No single n tells those two jobs apart.

Here is the claim that catches people. "My primality test is linear — it just tries every divisor up to n." Linear in what? The input is a number somebody wrote down, say twenty digits.

Its value is around a hundred quintillion (10²⁰), so the loop runs about a hundred quintillion times — 3,000 years at a billion divisions a second.
Its input is twenty digits, about 66 bits (log₂ of 10²⁰ ≈ 66.4).

Trying every divisor is linear in the value, which makes it exponential in the input, because one more digit multiplies the work by ten. Same algorithm, same work, two declared sizes, two opposite verdicts — and both verdicts computed correctly. Flip the toggle and watch "linear" become "exponential" with nothing else on the screen changing.

Look back over the last two sections and you will notice we climbed a ladder without naming it. It has exactly three rungs, and each one throws away something specific. The discard is the part worth knowing.

Rung one. Count every line's executions exactly, with that line's real cost on this machine. That is where a profiler lives, and it answers "which line should I touch?"
Rung two. Replace the per-line costs with anonymous constants and you get a·n² + b·n + c. On this page rung two is 2n² against 50 n log₂ n — the pairs method's 2 and the halving method's 50 are exactly the kind of constant those letters stand for. You have thrown away the machine and kept the shape, small-n behaviour included.
Rung three. Keep only the fastest-growing term and drop its coefficient, leaving n². At ten million records that is a hundred trillion (n² = (10⁷)² = 10¹⁴), and the 2 that stood in front of it is gone. You have thrown away the constants and kept the growth — and this rung is only trustworthy for large n.

Naming the discard is the whole skill, because it is what tells you when to climb back down. The duel in section 1 was a rung-two argument, not a rung-three one. Rung three says the halving method wins, and then it stops talking. The entire question of where it starts winning — at n = 471,000, on the numbers we chose — is built out of three numbers rung three throws away: the halving method's 50, the pairs method's 2, and the thousand-fold machine gap. Those three set the crossing at n = 25,000 log₂ n (50 × 1,000 ÷ 2), which settles at 471,000. Take the machine gap away and the same two methods cross at n = 189 — a different answer to the same question. So an engineer who only ever reasons on rung three cannot answer the question their team is actually asking. Click the greyed-out items in the figure and each one tells you which question it used to answer.

04Which input, and what the bound promises

There is a lie of omission built into "this algorithm takes n² time", and one experiment surfaces it. Take the insertion method — it grows an ordered region one item at a time, pushing each new item back past everything larger than it. Now hand it forty items twice.

Already in order: it looks at each item once, finds nothing to move, and walks straight out in 39 comparisons and zero moves (n − 1, with n = 40).
Exactly reversed: every item travels the whole way back, which is 780 comparisons and 780 moves (n(n−1)/2 = 40 × 39 ÷ 2).

Same algorithm, same forty items, and the work differs twenty-fold. Twenty is n/2 here, so at ten million items the same two inputs would differ five-million-fold. One number per algorithm is therefore not yet a fact. It becomes a fact when you say which input it is about.

Three candidates present themselves and only two are worth anything. The worst case is the default, and it earns that by being a promise — an upper bound over every input is a thing you can hang a deadline on. When a payments service commits to answering a card authorisation inside 300 milliseconds, that is a worst-case claim, and it is the only kind you can build on. "Averages 40 milliseconds" is a description of last month. The average case is genuinely the right question when a batch job runs overnight and only the total matters. It costs you something real to compute, though — you cannot average over inputs without knowing how likely each input is, and usually you don't. There is a good move for that situation and it is not on this page. You make your own choices random instead of assuming the input is. That is a page of its own.

And then the best case, which you should never accept as a headline again after the next question. How would you give almost any algorithm a brilliant best case? Add one line at the top — check for some input you can answer instantly, and return. That's it. That's the whole trick. On forty items the pairs method costs 780 comparisons whatever order they arrive in; add that one line and the already-ordered column drops to 39, a 20-fold best case you can put on a slide, while nothing else about the algorithm has changed by one operation. A number anyone can manufacture in one line tells you nothing about the algorithm underneath it. The figure lets you do it yourself. Press the button that inserts the shortcut, then watch carefully which counters move.

So you now have a working detector for a gamed benchmark. "Twenty times faster" invites exactly one question: on what input? If the answer is "mostly-ordered data" and the algorithm has an early exit, you have learned nothing about your workload unless your data is also mostly ordered — and the two columns that got 0.13% worse never made the slide. Notice the honest half of that, though, because this is not fraud. An early exit is a real optimisation and it really does help data that really is nearly ordered. The dishonesty is only ever in the headline that declines to say which input produced the number.

Now the notation, which is worth having only because it lets you state precisely which of those three cases you are claiming. Three symbols carry all of it, and the insertion method's own counts cash every one of them out at forty items, where n² is 1,600 (40² = 1,600).

O(g) is a ceiling: past some size, the cost stays below a constant multiple of g. The insertion method is O(n²), and its 780 comparisons sit under 1,600 (780 ≤ 1 × 1,600).
Ω(g) is a floor: the cost stays above a constant multiple of g. On reversed input the insertion method is Ω(n²), and 780 sits above a quarter of 1,600 (780 ≥ 0.25 × 1,600 = 400).
Θ(g) is both at once — the cost pinned between two multiples of g. On reversed input the insertion method is Θ(n²), because 780 sits between a quarter of 1,600 and a half of it (400 ≤ 780 ≤ 800, i.e. n²/4 ≤ n(n−1)/2 ≤ n²/2), and it stays inside that sandwich for every larger n.

Ceiling, floor, pinned. That is the whole vocabulary, and by now the constants inside those definitions need no defending — a shape is exactly what survives when you delete the machine, which is what rung three did.

And here is the part that gets misread constantly, so we will go slowly. A ceiling on the maximum is a ceiling on everything.

"This method is O(n²)" is a blanket claim, true of every input — including the already-ordered one, where it is true and very loose indeed: 39 comparisons is a long way under 1,600.
"Its worst case is Θ(n²)" tells you nothing whatsoever about the ordered input, which runs in Θ(n) — 39 comparisons at forty items, not 780. Θ pins one function tightly; the worst case is one function; every other input is out of scope.
"This method is Ω(n²)" is really a claim about the best case, and that makes it the strangest of the three. A floor that has to hold for every input is pinned by the fastest input, and our fastest input is the ordered one at 39 comparisons — nowhere near the 400 that floor demands. So that sentence is simply false. Say "its worst case is Ω(n²)" and it is true.

One word, and the sentence changes from wrong to right.

One sentence tests whether you own it: "algorithm A runs in at least O(n²)." Sit with that for a second. O is already a ceiling, so "at least a ceiling" rules out nothing at all — a constant-time algorithm satisfies it, because 1 sits under a multiple of n² just as surely as 780 does (1 ≤ 1 × n² for every n ≥ 1). Seven candidate shapes go in and zero are ruled out. It is the most common misuse in blog posts, papers and interview answers, and the goal is for it to look empty to you rather than merely wrong. Throw the candidates at it in the figure and watch every single one walk through.

05Size is not the only dial

Two things still move the running time and neither one is n: how disordered your data already is, and which operation you are counting. Both are places where a bound that is perfectly correct will send you off to optimise the wrong thing, which is a specific and expensive kind of being right.

The first dial is disorder. "Nearly sorted data is fast" is a real effect and a useless phrase, because "nearly" is not a quantity. So let's make it one. An inversion is a pair of items sitting in the wrong order relative to each other.

An ordered list of twelve items has 0 inversions.
A reversed list of twelve items has every pair inverted, which is 66 of them (n(n−1)/2 = 12 × 11 ÷ 2).

Now look again at the insertion method. Every shift it performs moves one item past exactly one larger item, so every shift destroys exactly one inversion, and it stops when there are none left. Its cost is therefore not n² at all. Its cost is n plus the number of inversions — twelve items reversed costs 12 + 66, twelve items ordered costs 12 + 0. That single quantity explains the linear best case, the quadratic worst case and "nearly sorted is fast" all at once: three explanations for the price of one measurement.

Watch the arcs disappear in the figure and the claim stops being something I told you. The counter reaches zero on exactly the step the list becomes ordered. Never before it, never after it.

What that buys is a running time parameterised by something other than size, and it changes the question you are able to answer. "How fast on 100,000 records?" has no answer. "How fast on my 100,000 records, which arrive roughly in time order out of a log?" does. Count the inversions in a sample and you have a real estimate. Notice that this is measurement again, the same move as the crossover in section 1. Twice now, the useful number has come from looking at the actual data rather than at the shape of the algorithm.

The second dial is which operation you are counting, and this is a trap I have walked into personally. The inner loop of that insertion method is doing two different jobs at the same time. It searches for where the new item belongs, and it shifts items rightward to open the gap. Searching costs comparisons. Shifting costs moves. They are separate budgets, and nothing whatsoever forces them to be equal.

So here is an obvious improvement, and it is genuinely obvious, which is why it is a good trap. The region you are searching is already in order, so stop scanning it and binary search it instead. Finding one slot among a thousand ordered items drops from about a thousand comparisons to about 10 (log₂ j with j = 1,000, and log₂ of 1,000 ≈ 10). Over the whole run of a thousand items that is 250,000 comparisons (n²/4 with n = 1,000) down to 8,500 (the sum of log₂ j for j = 1…1,000 ≈ 8,529) — a 29-fold cut. And the running time barely moves: 24% better, not 29 times better. You still have to shift the same 250,000 items to open the same gaps, the growth is still n², and the comparisons were never the bill. Run both in the figure and watch the comparison counter collapse while the move counter refuses to care.

That is worth generalising, because the ratio between those two budgets is set by what you are sorting and not by how you sort it. Comparing two 64-bit integers is one instruction; comparing two customer names is a function call that walks memory. Moving an 8-byte number is one instruction; moving a 400-byte record is fifty (400 ÷ 8 = 50 word-sized moves). So there are real situations where you happily pay more comparisons to make fewer moves — sorting large records, or writing to flash storage, where every write physically wears the device. Cost is a vector rather than a number, and optimising the wrong component of it buys you exactly nothing.

One last calibration, and then a confession about what this page skipped. A function can be genuinely unbounded and still never get past 5 in this universe. All the growth talk above is about n heading off to infinity, and your n is not infinity. Take this function: how many times must you take the logarithm of n before the result drops to 1 or below? Try n = 10⁸⁰, roughly the atom count of the observable universe. The chain runs 265.75, then 8.05, then 3.01, then 1.59, then 0.67 (log₂ of 10⁸⁰ = 265.75, log₂ of 265.75 = 8.05). Five logarithms. And it is five for every n from sixty-five thousand up to 2⁶⁵⁵³⁶, a number with 19,729 digits (65,536 × log₁₀2 ≈ 19,728.3). So a cost of "n times that function" is a linear cost wearing a frightening hat.

And it cuts the other way too, which is the direction that actually bites. A factor the notation calls constant can be 1.1 trillion (2⁴⁰ = 1,099,511,627,776), and the notation will not say a word about it — 2⁴⁰·n and n are both simply "linear". So the last question to ask of any bound is not "which one grows more slowly?" It is "at the sizes I actually have, which one is smaller?" And once again, that is measured. Every genuinely useful number on this page came from measuring something.

What we did not do here is prove anything. Everything above is a mechanism you watched work, which is a different and weaker thing than a proof. Where that difference matters I would rather say so than hope you don't notice. Fig 13 is the clearest case. The counters agree on every input you can throw at it, and "no counterexample found" is not the same statement as "no counterexample exists". A proof of that one is short, and it is not here.

There is also something in section 2 that we only half used. The candidate count does not merely warn you off enumerating — it hands you a floor. Suppose there are 20! possible orderings, 2.4 quintillion of them, and every question you are allowed to ask comes back with one bit. Then 61 questions cannot be enough, because 61 bits can only tell 2.3 quintillion possibilities apart (2⁶¹ = 2,305,843,009,213,693,952), and that is less than 20!. 62 is the floor, and no amount of cleverness gets under it. Nobody has to invent an algorithm for that to be true. It is a fact about the answer set, and it was sitting inside the counting we already did. That is the next constraint: you only get one bit per question, and it decides in advance exactly how good sorting is ever allowed to get.