A design review calls an n^100 algorithm efficient because it is polynomial; what does that line actually concede?
answer
- necessary, not sufficient
- a shape claim, not a budget
- some exponent, not a small one
- constants and crossover quantified away
- worst case, not the case you meet
basics
~20 sIt concedes the exponent, the constant factor, the crossover point and the average case. Polynomial time promises that the cost curve bends the right way as the input grows without bound; it promises nothing at the sizes a system will actually see.
solid answer
~50 sMembership in the polynomial-time class requires only that *some* fixed exponent exists, so an algorithm needing `n^100` steps qualifies while finishing no instance anyone will ever construct. The definition also ignores constant factors entirely, says nothing about where two curves cross, and is stated for the worst case, so a method with an exponential worst case may still beat it on every instance a team meets. The line is kept because it is the only definition that survives a change of machine model and stays intact when routines compose — which makes it the right boundary for research and the right first-order prior in a discussion. It is not a capacity plan. The follow-up a lead owes the review is: what is the exponent, what is the constant, and at what input size does this become the better choice?
go deeper
Learn the two-word version: polynomial is necessary, not sufficient. It tells you the approach is not explosive; it does not tell you the job finishes tonight.
Name the four things the definition quantifies away — exponent, constant factor, crossover point and the case being measured — and be able to say which of them your own benchmark answers.
Bring measurement to the argument: expected sizes, the constant you observed, and where the crossover sits relative to production. Do not reject a method purely because its worst case is exponential.
Hold both roles at once. Use the class to kill plans on the wrong side of the line and to steer research effort, and use measured numbers for capacity. Say explicitly which of those two decisions the meeting is making.
## What the polynomial verdict promises 'This is polynomial time' is a precise statement with a narrow scope: there exist constants `c` and `k`, fixed once and for all, such that every instance of length `n` is decided within `c * n^k` steps. It is a claim about the **shape** of the curve as `n` grows without bound, and about the worst instance at each length. Everything a capacity conversation needs lives in the parts the statement quantifies away. ## The four concessions 1. **The exponent.** `k` may be any constant. An algorithm at `n^100` is a member in good standing and will not finish a ten-element instance in the life of the universe. The class was never designed to discriminate here, and a result can be a genuine breakthrough — proving a problem is tractable in principle — while being unusable in every implementation. 2. **The constant factor.** `c` is quantified away entirely. Two algorithms with the same exponent can differ by orders of magnitude, and that difference is invisible to the classification and decisive in production. 3. **The crossover.** The class compares behaviour in the limit. It does not say at which input size the polynomial method overtakes the exponential one, and for the sizes a given system handles, the crossover may be far to the right of anything that will ever be run. 4. **The case being measured.** The bound is worst-case. A method whose worst case is exponential can be reliable on structured real-world instances, and a worst-case polynomial method can be the slower choice in practice on every input the system sees. ## Why the line is still the right one to hold None of that is an argument for abandoning it, and a lead who treats the class as meaningless has swapped one error for another: - It is the only definition of efficiency that **survives a change of machine model**, so results stay portable. - It is **closed under composition**, so a polynomial-time result can be used as a black box inside a larger algorithm. - It is **provable**, unlike any wall-clock claim, which can only be measured on a machine that will be replaced. - Empirically, the natural polynomial algorithms discovered for natural problems have mostly landed at small exponents, so the class has been a better predictor of practical tractability than its worst cases would suggest. - Crossing the line in the other direction — discovering a problem is *not* known to be tractable — genuinely changes a plan, because it redirects effort from exact methods toward approximation, restriction or search. ## The questions a review should actually ask | what was claimed | what to ask for | |---|---| | 'it is polynomial' | the exponent and the constant factor, stated | | 'it scales' | the input sizes expected in eighteen months | | 'it beats the old method' | the crossover point, and whether production sits above it | | 'the bound is proven' | which case the bound covers, and what the typical case does | | 'it is the theoretically best known' | whether the implementation exists and has been measured | ## The judgment a lead owns The mistake in the review is not using complexity classes; it is letting a qualitative boundary stand in for a quantitative budget. The two do different jobs: - **The class answers a design question**: is this approach on the tractable side of the line at all, or are we planning to brute-force something that grows explosively? A negative answer there should stop a project regardless of current data volumes. - **Measurement answers the capacity question**: at our sizes, on our hardware, with our data, how long does it take and how does that change as we grow? Use the class to reject the plans that cannot work and to decide where to spend research effort; use measured numbers to decide what to ship. A claim that an approach is polynomial and therefore fine has skipped the second job, and a claim that complexity theory is academic has skipped the first. The answer that lands in an interview names both roles and gives the concrete follow-up: *polynomial is necessary, not sufficient — tell me the exponent, the constant, and the size where it wins.*
- If the class admits n^100, why has it predicted practical tractability so well?Because the polynomial algorithms actually discovered for natural problems have mostly had small exponents. That is an empirical observation about the problems people care about, not a consequence of the definition, so it is a useful prior rather than a guarantee — and the exceptions are real.
- An exponential-worst-case method handles every instance your team meets in under a second. What does that tell you?That the worst case is not the case you are in. Real instances often carry structure that the worst-case analysis must ignore, so such methods can be the correct engineering choice. What you owe the decision is a statement of what happens when an adversarial or merely unusual instance does arrive.
- Where is the class boundary genuinely decision-changing rather than academic?When a problem is not known to be tractable at all. That finding redirects a plan away from an exact general algorithm toward approximation, a restricted parameter, a solver, or a frank heuristic — a change of strategy no amount of profiling would have suggested.
Knowing a vehicle is road-legal tells you it may be driven and nothing about whether it can carry your load by Friday; you still ask for the payload and the timetable.
saying these in an interview costs you the question
- Treats a polynomial bound as evidence the system will be fast.
- Dismisses complexity classes as academic because they admit huge exponents.
- Compares two algorithms by exponent alone, ignoring constants.
- Assumes a worst-case bound describes typical production instances.
- Never asks at what input size one method overtakes another.
- Treats an unimplemented theoretical result as an available option.