Complexity is a claim about a model, and the model is the argument

An interface is a promise about time. The list scrolls, the suggestions appear as you type, and the map redraws. A choice of data structure keeps or breaks each promise. That choice is usually defended with a complexity bound: this loop is O(n), that lookup is O(log n), so take the second.

This first of ten units argues that a complexity bound is not a fact about a program. A bound is a theorem about a stated machine and a stated measure of work. It predicts an interface's behaviour exactly where those stipulations hold. The premises are chosen rather than given.

A bound is proved about a machine and a measure of work

Hartmanis and Stearns (1965) are usually remembered for a hierarchy of complexity classes, but the durable move in their paper is a definition. They measured the complexity of a computation by how fast a multitape Turing machine can print out the terms of a sequence. Difficulty thus became a relation between a problem and a chosen machine rather than a property of the problem alone. Arora and Barak (2009) set out the subject on the same footing: their graduate text defines Turing machines and the basic time and space classes before it proves anything about them. A bound arrives with a model attached.

Cook (1971) fixed the meaning of the word efficient. He showed that any problem solvable by a polynomial-time nondeterministic Turing machine reduces in polynomial time to deciding whether a propositional formula is a tautology, so the difficulty of an entire class could be concentrated in one problem. Karp (1972) showed that the reduction travels: satisfiability was carried to other combinatorial problems, and each inherited the hardness, so a bound stopped describing one algorithm and became a claim about a class. Cook (1983) surveyed that programme. Garey and Johnson (1979) turned the theory into a design instrument, assembling a catalogue of hard problems so a practitioner could recognise an intractable problem rather than search for an algorithm that provably does not exist.

Cook's proof shows what that stipulation costs: for a stated machine and a polynomial time bound it builds a formula whose clauses assert that the first row is the input, that each later row follows by a transition rule, and that an accepting state is reached, satisfiable exactly when that machine accepts that input.

A lower bound is a theorem about the machine the proof was written for. It says nothing about a different machine with different costs.

Choosing a case is choosing a model

The most familiar way a model is chosen is the choice of case. Cormen, Leiserson, Rivest and Stein (2022) give the standard apparatus of worst-case, average-case and amortised analysis. The fourth edition adds chapters on matchings in bipartite graphs, online algorithms and machine learning. A worst-case bound describes every input of a given size. An average-case bound describes how inputs arrive, and it is only as good as the model of arrival. An amortised bound describes a sequence of operations rather than any one of them.

A growable array is the worked case. Appending to a full array copies every stored element into a block twice the size. That single append therefore costs time proportional to the number of elements already there. A run of appends pays for a copy once every doubling, so n appends together cost time proportional to n, not to n times n. Tarjan (1985) makes the accounting exact.

Tarjan (1985) gave the amortised case its technique. He averaged over time to turn a sequence of operations into one bound, and the technique yielded self-adjusting structures designed against it. The measure is a sequence, not an instant, so the bound says nothing about the single operation a user happened to trigger, the one a person on a low-cost device feels as a stall. Knuth (1976) had already defined Omicron, Omega and Theta so that an upper bound, a lower bound and a tight bound are three separate statements rather than one. The choice among the cases is therefore a modelling decision.

The measure of work is chosen too. Cormen and colleagues count comparisons and memory accesses within a stated cost model. A bound proved under one count need not survive another, because an operation free in the abstract model can dominate on a real device.

The measure is a choice, and the field now says so

This is not a critique invented outside the discipline. Roughgarden (2020) gathers forty contributing researchers to argue that there is no single method for analysing algorithms, since the most enlightening method depends on the problem. Spielman and Teng (2004) give the clearest example. Smoothed analysis measures the worst-case expected performance under small perturbations of the input, interpolating between the worst and the average case, and shows that the simplex algorithm has smoothed complexity polynomial in the input size and the standard deviation of the perturbations. The algorithm did not change between the two accounts. The model did.

The modern theory of hardness makes the same point from the other direction. Abboud, Vassilevska Williams and Yu (2015) note that most conditional lower bounds rest on one of three famous hypotheses: the 3-SUM conjecture, the all-pairs shortest paths conjecture and the strong exponential time hypothesis. Only circumstantial evidence supports them, and no formal relationship between them is known. Abboud and colleagues then assume the weaker conjecture that at least one of the three is true, and from it derive tight lower bounds for triangle problems and for the amortised update and query times of dynamic reachability. That such a condition can fail was demonstrated in October 2026. Alman and Vassilevska Williams (2026) gave the first polynomial improvements over the textbook algorithms, solving 3SUM on n integers in O(n^1.9992) and all-pairs shortest paths in O(n^2.9995) time, and so refuted both hypotheses. Known reductions carry the refutation to Exact Triangle and Zero-Weight k-Clique, so lower bounds reduced from those assumptions are vacuous rather than false. Fischer (2026) recovers many 3SUM-hard geometric lower bounds under a different assumption. What counts as efficient depends on which conjecture one assumes, and on whether that conjecture still stands.

Contested question: is a bound a prediction, or a premise for measurement?

The literature disagrees about what an asymptotic analysis is for. The first position treats the bound as the analysis itself and the theorem as the deliverable. Cook (1983) states it plainly. The work is to define a problem's intrinsic complexity and to prove upper and lower bounds for it, and probabilistic and parallel computation extend the same programme rather than departing from it. On this view a proved bound is the answer, and an observed running time is an implementation detail.

The second position treats the bound as the opening move of an empirical investigation. McGeoch (1996) surveys the design, execution and reporting of computational experiments on algorithms, treats an algorithm as an abstract model of an implemented program studied by measurement, and sets out the discipline that turns a timing into evidence. Johnson (2002), writing from the theoretician's side, argues that experimental analysis deserves to be a subject in its own right and offers a guide to how such work should be done. On this view a bound predicts nothing until it has been checked, and the check is the contribution.

A study would settle the disagreement. It would state its model, derive a bound, and then measure the same algorithm on inputs and machines inside that model. No source in this unit performs it: McGeoch and Johnson describe how such work should be done but do not run the comparison, and Roughgarden (2020), who comes closest to taking a side, argues that the model should be chosen to suit the problem rather than defending either pole.

Rate the two by the evidence behind them. Cook (1983) argues from theory, and his case is a programme rather than a measurement. McGeoch (1996) and Johnson (2002) offer methodology, not a fitted comparison, so the empirical side is a prescription. The strongest objection is that attaching a model to every bound adds a premise the reader cannot check. While the dispute is open, a designer states the machine and the measure beside the bound, then records where prediction and measurement part.

Where the argument is heading

The named work points one way. Roughgarden (2020) treats analysis as a portfolio indexed by problem, and Spielman and Teng (2004) supply the template for a model that interpolates between the extremes. Abboud, Vassilevska Williams and Yu (2015) show that hardness claims are becoming explicitly conditional, and Alman and Vassilevska Williams (2026) show how completely such a claim falls when its condition fails. The honest efficiency claim is therefore increasingly on this assumption, this result. Even the teaching text has moved: Cormen and colleagues (2022) add online algorithms and machine learning to a fourth edition whose core apparatus is unchanged. The direction of travel is a bound stated with its model attached. The interface claim says: on this model, this behaviour.

The sources this unit rests on

• Abboud, A., Vassilevska Williams, V. and Yu, H. (2015). Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. doi:10.1145/2746539.2746594 Abboud, Vassilevska Williams and Yu derive lower bounds for triangle problems from the assumption that one of three popular hypotheses holds, theory resting on an unproved conjecture. It is the unit's clearest case of a conditional bound, and two of its three assumptions have since been refuted.
• Alman, J. and Vassilevska Williams, V. (2026). Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs. arXiv preprint. https://arxiv.org/abs/2610.06783 Alman and Vassilevska Williams solve 3SUM in O(n^1.9992) and all-pairs shortest paths in O(n^2.9995) time with one thin-matrix-product algorithm. It is an unrefereed preprint carrying the unit's superseded condition.
• Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press. doi:10.1017/cbo9780511804090 Arora and Barak set out computational complexity as a graduate course, defining Turing machines and the time and space classes before proving anything. It is a textbook, and it states the framework the unit's thesis rests on.
• Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the third annual ACM symposium on Theory of computing - STOC '71. doi:10.1145/800157.805047 Cook shows that any problem a polynomial-time nondeterministic Turing machine can solve reduces in polynomial time to deciding whether a formula is a tautology. It is a proof, the origin of NP-completeness, and the boundary that makes efficient mean polynomial.
• Cook, S. A. (1983). An overview of computational complexity. Communications of the ACM. doi:10.1145/358141.358144 Cook surveys computational complexity, giving most weight to defining a problem's intrinsic complexity and proving upper and lower bounds together. It is a survey by a founder of the field, and it states the position the unit argues against.
• Fischer, N. (2026). Beyond 3SUM-Hardness for Geometric Problems. arXiv preprint. https://arxiv.org/abs/2610.32162 Fischer notes that many geometric problems' quadratic lower bounds lost their foundation when the 3SUM hypothesis fell, and recovers them under a different assumption with trivial changes to the proofs.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2022). Introduction to Algorithms. MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ The fourth edition of Introduction to Algorithms covers recurrences and worst-case, average-case and amortised analysis, and adds chapters on matchings, online algorithms and machine learning. It is the teaching standard the unit measures itself against.
• Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. https://archive.org/details/computersintract0000gare Garey and Johnson assemble NP-completeness with a catalogue of several hundred hard problems and a guide to proving a problem hard. It is a reference monograph, and it turned the hardness boundary into a design constraint.
• Hartmanis, J. and Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society. doi:10.1090/s0002-9947-1965-0170805-7 Hartmanis and Stearns measure a computation by how fast a multitape Turing machine prints a sequence, and prove the classes so defined form a proper hierarchy. It is a theorem about a chosen machine, and it establishes the unit's core claim.
• Johnson, D. (2002). A theoretician's guide to the experimental analysis of algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. doi:10.1090/dimacs/059/11 Johnson argues that theoretical and experimental analysis ask different questions and must be reported differently, and warns against experiments designed to confirm a theorem. It is methodology, and it supplies the unit's second contested position.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. Complexity of Computer Computations. doi:10.1007/978-1-4684-2001-2_9 Karp reduces satisfiability to twenty-one other combinatorial problems, so a polynomial algorithm for any one would give one for all. It is a proof by reduction, and it shows hardness is a claim about a class.
• Knuth, D. E. (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News. doi:10.1145/1008328.1008329 Knuth argues that the Omicron, Omega and Theta notations are routinely abused, and sets out conventions separating upper, lower and tight bounds. It is a notation paper, and it fixes the conventions the unit reads every bound with.
• McGeoch, C. C. (1996). Toward an Experimental Method for Algorithm Simulation. INFORMS Journal on Computing. doi:10.1287/ijoc.8.1.1 McGeoch surveys how computational experiments on algorithms should be designed, run and reported, treating an algorithm as an abstract model studied by measurement. It is methodology, and it is the unit's empirical counterpart to the proof.
• Roughgarden, T. (2020). Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press. doi:10.1017/9781108637435 Roughgarden's edited collection argues that there is no single method of algorithm analysis, and gathers smoothed, semi-random and beyond-worst-case frameworks in one place. It is contributed surveys, and it is the field's admission that the model is a design decision.
• Spielman, D. A. and Teng, S. H. (2004). Smoothed analysis of algorithms. Journal of the ACM. doi:10.1145/990308.990310 Spielman and Teng introduce smoothed analysis, measuring worst-case expected performance under small perturbations of the input, and show the simplex algorithm has polynomial smoothed complexity. It is a theorem about a model added around an unchanged algorithm.
• Tarjan, R. E. (1985). Amortized Computational Complexity. SIAM Journal on Algebraic Discrete Methods. doi:10.1137/0606031 Tarjan surveys amortisation and sets out the potential-function method that turns a sequence of operations into one bound, yielding self-adjusting structures. It gives the unit a bound whose meaning depends on the model of use.