The growth ladder

Two procedures answer the same question about a list: does any value appear twice? The first performs 100n + 1 steps on a list of n items, and the second performs n² + n + 1 steps. At ten items the first looks hopeless, because it takes 1,001 steps against 111, while at a hundred items the two are almost level, at 10,001 and 10,101. At a thousand items the second is ten times slower [S:15:224]. The procedure that lost at ten items draws level shortly below a hundred items and wins from then on, by a margin that grows, so the two orders swap once and never swap back.

The notation hides that crossing point, the input size where two costs change places. It also hides the constant in front of the leading term, the smaller terms that matter at small sizes, and every machine-specific factor. What it keeps is the response to scale, which is the part that decides the outcome once the input is large. !Two costs that trade places. At ten items 100n + 1 needs 1,001 steps and n squared + n + 1 needs 111, so the larger class is cheaper. They are level at 99 items, 9,901 each, and at a thousand the quadratic is ten times the cost. The lower rung does not win at every size; it wins only past the crossing. Status: re-simulated.

The standard ladder names the common shapes: constant, logarithmic, linear, linearithmic, quadratic, cubic and exponential [S:15:225]. A big-O statement keeps the fastest-growing term of a cost and drops the rest, up to a constant factor and for all inputs past some threshold [S:5:538]. Read O(n) as "grows no faster than n, times some fixed multiplier": the O carries no number and names no speed. The constant factor is that multiplier, which the notation throws away, and the threshold is the input size beyond which the comparison is promised to hold. So 100n + 1 and n + 1,000,000 both become O(n), while n² + n + 1 becomes O(n²), and the notation reports the class rather than the exact count. !Five rungs at n = 1,000: about ten steps for log base two of n, a thousand for n, ten thousand for n log n, a million for n squared, a billion for n cubed. The sixth rung, two to the n, is an arrow off the right edge. The rows on the left give the response to doubling. Status: re-simulated.

A logarithmic cost grows like the logarithm of the input. The logarithm base two of a number is the count of halvings that takes it down to one: the logarithm of 1,024 is 10, because two to the tenth power is 1,024. This chapter reads log with base two throughout, so a logarithmic procedure works through a thousand items in about ten halvings, since two to the tenth power is slightly above a thousand.

A linear procedure touches each item once, while a linearithmic procedure does n log₂ n steps: a thousand items cost a thousand times the logarithm of a thousand, which is about ten thousand. The quadratic rung reaches a million at the same size, and the cubic rung reaches a billion. By the exponential rung the cost doubles with every added item, so sixty items have already passed a quintillion steps, which is why that rung ends the ladder rather than sitting beside the others.

Dropping the constants is what makes the notation useful and what makes it dangerous, since two costs in the same class can differ by a factor of a thousand. A class is a set of costs that share a shape: they agree once you allow a fixed multiplier and ignore everything below the threshold.

The ladder becomes accurate only after the threshold, which is what its asymptotic behaviour means, and that is not a defect to be patched over but a boundary condition on the whole method. A prediction taken from the ladder is a statement about what happens when the input keeps growing, and the crossing point tells you where the prediction starts to apply.

Worked example. Take three procedures with costs n, n² and n³, and count their steps at two sizes.

Doubling the input doubles the linear cost, quadruples the quadratic cost, and multiplies the cubic cost by eight. The same response appears as a table in an OpenStax textbook, whose books are free to read online. A logarithmic cost gains one unit there, and an exponential cost is squared, because two to twice n is the square of two to the n [S:114:119].

$$C(2n)\approx 4C(n)\text{for a quadratic cost}$$

A quadratic cost multiplies by about four when the input doubles, and the word about carries the constant factor that the notation discarded.

The same arithmetic explains why the choice of algorithm beats the choice of machine. A program that is a thousand times faster buys you a factor of a thousand, which a change from n² to n can erase at a thousand items and dwarf at ten thousand. That is the practical content of the beginner question: a million steps against ten thousand is a difference of class, not a difference of hardware.

The ladder also explains why the same program can be fine in a demo and useless in production. At a hundred rows most rungs are quick enough, and at a million rows only the bottom rungs finish in a reasonable time. The crossing point is where the class of the cost starts to matter more than the constants, and finding it is a measurement, not a proof.

The notation's cost is that it cannot rank two algorithms of the same class, and it says nothing useful below the threshold where the leading term takes over. When two costs share a class, only the constants and the machine can separate them, and the notation has thrown those away on purpose [S:11:26]. Constants are not a detail to be waved away; they are the whole answer at the sizes most programs actually meet.

The formal statement. Take functions from the positive integers to the non-negative reals. Write $f=O(g)$ when there are constants $c>0$ and $n_0$ such that $f(n)\le cg(n)$ for every $n\ge n_0$ [S:11:24][S:5:538]. Write $f=\Omega (g)$ when $g=O(f)$, and $f=\Theta (g)$ when both hold [S:5:539][S:5:541]. Write $f=o(g)$ when the ratio $f(n)/g(n)$ tends to zero [S:5:536]. Every one of these is an eventual statement: it says nothing about inputs below $n_0$, and it compares functions rather than programs.

The derivation. Dropping lower-order terms is a chain of inequalities, and the constants are the whole content. Take $5n{\log }_{2}n+8n-200$. For $n\ge 2$ the term $-200$ is at most zero, so you drop it. For $n\ge 2$ you have ${\log }_{2}n\ge 1$, so $8n\le 8n{\log }_{2}n$. Adding the two surviving terms gives $13n{\log }_{2}n$, so the function is in $O(n{\log }_{2}n)$ with $c=13$ and $n_0=2$ [S:11:24]. The same three moves prove the polynomial case in general.

The edge case. The rule that a constant factor does not change the class is about multiplying a function, not about putting a constant in the exponent. The function $4^x$ is not $O(2^x)$, even though $4$ is a constant multiple of $2$, because $4^x=(2^x{)}^2$ [S:5:540]. A constant difference in the base becomes a squared ratio, and the gap grows without limit. The core's ladder would put both functions on the exponential rung, and the formal definition separates them.

A second edge. Big-O is one-sided. An algorithm that is $O(n^2)$ is also $O(n^3)$, so the statement does not name a class. The core wrote "becomes $O(n^2)$" as shorthand. The two-sided statement is $\Theta$, and the ladder is only meaningful in $\Theta$ [S:5:539]. The same care applies to sums: $n$ terms that are each $O(1)$ add to $O(n)$, not to $O(1)$, because the bound is a relation between functions and not a number [S:5:540].

Where the ladder breaks. The ladder suggests ordered rungs with nothing between them. Karatsuba multiplication sits at $n^{{\log }_{2}3}$, between the linearithmic and quadratic rungs, and no rung names it. The ladder also suggests that a big-O statement names a class, while it gives an upper bound only. Use the ladder for the response to doubling, and use the definition for anything finer.

What the core hid. The core named the constant and the threshold, so it hid neither. What it did not state is that $O$ is one-sided, that a class claim needs $\Theta$, and that a constant in an exponent is not a constant factor. All three leave the ladder's advice intact, because the core compared classes and the formal statements agree wherever it spoke of a class.

Original sources. The symbol $O$ comes from number theory: Paul Bachmann used it as early as 1894, before it described running times [S:11:25]. The definitions you met are the standard ones, stated with constants $c$ and $n_0$ [S:5:538], and little-o is stated with a limit [S:5:536]. Theta and Omega are defined from $O$ [S:5:539][S:5:541]. The ladder of names is a teaching device rather than a theorem; Downey lists the rungs in increasing order of badness [S:15:225].

An open question. Is there an $O(n^2)$ procedure for matrix multiplication? The question is open, and the text that raises it calls such a procedure conceivable but unknown [S:5:539]. Evidence that would settle it: an explicit algorithm whose exponent is two, or a proof that no exponent below the current best is possible.

A frontier result. Neural scaling laws fit a loss curve of the form $L(x)=a{x}^b+{ϵ}_{\infty }$, which is a power law plus an irreducible term [S:91:72]. The Chinchilla form adds one power law for model size and one for data [S:91:72]. This is the growth ladder turned into a measurement: the exponent is estimated from small runs, and the fit decides how to spend a compute budget. The reasoning matches 5.2, with the caveat that a fitted power law has no threshold and no proof.

A note on the other symbol. Theta is what a claim about a class needs, and Omega is what a claim about a wall needs. Omega appears again in 5.4, where the lower bound on comparison sorting is a statement in Omega.

What to read next. Read section 13.7 of Mathematics for Computer Science for the definitions, the Theta notation and the list of pitfalls [S:5:539]. Read section 1.3.3 of Open Data Structures for the same definitions with worked constants [S:11:24]. Then read the scaling-law section of Xiao and Zhu to see the notation used on a measured curve [S:91:72].