Why does complexity theory draw the line for 'efficient' at polynomial running time rather than at a fixed step budget?
answer
- a claim about scaling, not hardware
- a budget dates, a curve does not
- must survive changing the machine model
- routines call routines
- doubling n: constant factor versus squaring
basics
~20 sPolynomial time is a claim about scaling, not about one machine. A polynomial bound survives a change of machine model and stays polynomial when routines call each other; a fixed step budget expires with the next hardware or the next larger input.
solid answer
~50 sA fixed budget like 'a billion steps' is not a property of an algorithm at all, only of an algorithm on one input size, and it dates the moment hardware or the workload changes. Polynomial time is a property of the growth curve: cost at most `c * n^k` for constants fixed in advance, where `n` is the length of the written-down input. Two things make that the natural line. It is robust — reasonable sequential machine models simulate each other with only polynomial overhead, so the verdict does not depend on which one you picked. And it composes — a polynomial number of calls to a polynomial routine is still polynomial, so you can use a result as a black box. Doubling the input multiplies a polynomial cost by a constant; it squares an exponential one.
go deeper
Be able to say that polynomial time describes how cost grows with the size of the input, and that the alternative — a fixed number of steps or seconds — is not a property of an algorithm at all.
Explain the two structural reasons: a polynomial bound survives translation between reasonable machine models, and composing polynomial-time routines leaves you inside the class. Show the doubling contrast rather than asserting it.
Hold both sides at once in a design discussion: defend the line as the only robust definition available, and still insist on the exponent, the constant and the expected input sizes before calling anything fast enough.
The tradeoff to articulate is coarseness bought in exchange for robustness. A definition tight enough to predict runtimes would be tied to a machine and would not compose, which is exactly why the field accepted a line that admits absurd exponents.
## What the polynomial line actually says The class **P** holds the decision problems for which some algorithm answers *every* instance within `c * n^k` steps, where `n` is the number of symbols needed to write the instance down and `c` and `k` are constants chosen once, in advance, for all instances of every size. Notice what the sentence does not contain: no seconds, no hardware, no budget. It is a claim about the **shape** of the cost curve, not its height. That choice was deliberate. Three candidate definitions of 'efficient' were available: 1. **A fixed step budget** — 'at most a billion steps'. This is not a property of an algorithm; it is a property of an algorithm *together with one input size*. Hand it a file twice as large and the claim silently dies. 2. **A fixed wall-clock budget** — 'under one second'. This cannot be proved about an algorithm at all, only measured about a run, on a machine that will be replaced. 3. **A growth rate** — 'the cost is bounded by some polynomial in the input length'. This survives both a bigger input and a different machine, and it is the one the field adopted. ## The two properties that do the work - **Robustness across models.** Reasonable deterministic sequential machine models simulate one another with only polynomial overhead, so 'runs in polynomial time' means the same thing whichever you define it on. A step-count budget does not survive that translation; a polynomial one does. - **Closure under composition.** Real code calls subroutines. Substituting one polynomial into another yields a polynomial, so a polynomial number of calls to a polynomial-time routine is still polynomial. This is what lets a polynomial-time result be used as a black box inside a larger algorithm without redoing the analysis. - **Closure under the ordinary combinators.** Sequencing, bounded loops, and mapping one problem onto another all preserve the bound, so the class is stable under the way programs are actually assembled. - **A single closed class.** Because of the two closures above, P is closed under the operations that matter, which is exactly what makes it usable as a hypothesis in proofs about other problems. No fixed budget has any of these properties. 'Under a billion steps' is not closed under composition: two such routines in sequence already break it. ## The gap the line is drawing The reason the line lands between polynomial and exponential, rather than between quadratic and cubic, is what happens when the input doubles. | bound | cost at n | cost at 2n | effect of doubling the input | |---|---|---|---| | n | n | 2n | multiplied by 2 | | n squared | n^2 | 4 n^2 | multiplied by 4 | | n cubed | n^3 | 8 n^3 | multiplied by 8 | | 2^n | 2^n | (2^n)^2 | the cost is **squared** | Every polynomial row is multiplied by a constant, `2^k`, that does not depend on `n`. The exponential row is squared. That is a difference in kind, not in degree, and it is why the two sides of the line behave differently under every change you might make: a machine ten times faster buys a polynomial algorithm a meaningfully larger input, while it buys an exponential one roughly three or four extra elements. ## What the line concedes Being honest about this is part of the answer, not an objection to it: - An algorithm running in `n^100` steps is in P, and no input anyone will ever build makes it finish. - Constant factors are outside the definition entirely. - The bound is worst-case, so a method with an exponential worst case can still be the right tool for the instances a team actually meets. The line is a research boundary and a first-order prior, not a capacity plan. It answers 'does the cost curve bend the right way?' — and then someone still has to ask for the exponent and the constant. ## Saying it in an interview The compact version is three sentences: polynomial time is a statement about how cost scales with input length, not about a step count; it was chosen because polynomial bounds survive a change of machine model and stay polynomial when routines compose, which no fixed budget does; and the price of that robustness is that the class is coarse at both ends.
- When the input doubles, what separates a cubic bound from an exponential one?A cubic bound is multiplied by eight, a constant that does not depend on the input length. An exponential bound is squared: the cost at twice the length is the old cost multiplied by itself. That is why a faster machine moves the reachable input size a long way for a polynomial algorithm and barely at all for an exponential one.
- Can an exponential-time algorithm ever be the right choice over a polynomial one?Yes. The class compares growth rates as the input grows without bound, not costs at the sizes you meet. An exponential method with a tiny constant can win on small instances, and a polynomial one with a huge exponent or constant can lose on every instance that exists. The class tells you which one eventually wins, not which one to ship.
- Why does closure under composition matter so much for a definition of efficiency?Because algorithms are built from other algorithms. If the efficient class were not closed under calling a routine a polynomial number of times, every result would have to be re-derived in its calling context, and no result could be reused as a black box. Polynomials compose; fixed step budgets do not.
A speed limit posted in miles per hour still means something after you buy a faster car; a rule saying 'finish the trip in twenty minutes' stops meaning anything the moment the route changes.
saying these in an interview costs you the question
- Says polynomial time means the algorithm is fast in practice.
- Treats the line as a step count measured on current hardware.
- Claims an exponential-time algorithm is unusable at every input size.
- Believes membership in the class requires a small exponent.
- Says polynomial is preferred because its constant factors are smaller.
- Cannot say what n refers to in the bound.