Maths/Big O notation

What O(f) actually is

After thiswhat you will be able to doTest whether a cost belongs to O(f) by producing a valid multiplier and threshold, and explain why O(f) is a set rather than one value.

Questionwhat this lesson answersWe write T(n) = O(n^2) with an equals sign, yet you cannot swap the two sides and the right side is not a single number. What kind of object is O(n^2), such that a cost can be said to equal it?

Not coveredwhat this lesson leaves outWe define what it means to belong to O(f) and we find the two witnesses by hand for one function. We do not prove the rules for combining O(...) expressions, and we leave the lower bound alone.

There is a strange convention in algorithm writing. We write ${T(n) = O(n^2)}$ with an equals sign, even though the line is not an ordinary equality. You would never turn it around and write ${O(n^2) = T(n)}$. The left side is a rule that gives a step count for each input size. The right side is not one number at all, and it does not even stand for one particular cost. So the equals sign is standing in for something else, and the rest of this lesson is about what.

First notice what the left side is. A rule that takes an input and returns a number is called a function. The cost rule ${T}$ takes an input size and returns a number of steps. A collection can hold more than one such rule, just as a shelf can hold more than one book. In mathematics, a collection treated as one object is called a set. To say that one thing is among the things in a set is called membership.

That is the kind of object on the right. ${O(n^2)}$ is a set of functions, not a number and not one function. It contains every cost rule whose growth can be kept under some fixed multiple of ${n^2}$ once the input is large enough. The honest statement is ${T \in O(n^2)}$: ${T}$ belongs to that set. The equals sign is standard shorthand, but it hides the membership claim and encourages the wrong picture.

What it takes to belong

We need a test for that claim. Write ${f}$ for the comparison rule, the shape we are using as a ceiling, and write ${g}$ for the cost rule under examination. The test asks for two ordinary numbers. First, find a positive fixed multiplier that lifts the comparison rule high enough. Call that multiplier ${c}$. Then find a starting input after which the lifted comparison rule never falls below the cost. Call that starting point ${n_0}$, pronounced “n zero”. A starting point of this kind is a threshold.

Those numbers are not decoration. Producing them is the evidence for the claim, so they are called witnesses. One witness says how high the ceiling is. The other says where we are allowed to begin asking it to cover the cost. Before that point the cost may do anything. After that point, every input must obey the comparison. A cost is never below zero, which accounts for the first comparison in the definition:

The symbol ${\exists}$ reads “there exists”. It is a demand to hand over an actual ${c}$ and an actual ${n_0}$, not a promise that they feel plausible. The phrase “for all” is just as strict: one lucky large input is not enough. The ceiling has to stay above the cost from the threshold onward.

Find the witnesses

Return to the running cost. Here the cost rule and comparison rule are

Try a ceiling multiplier of ${c = 4}$. We need to know when the full cost is at most four copies of the comparison shape. Moving everything to one side turns that question into this:

The right side first becomes at least zero, or nonnegative, at ${n = 538}$. The two neighbouring inputs make the cutoff visible:

So ${c = 4}$ and ${n_0 = 538}$ are witnesses. From input ${538}$ onward, the ceiling ${4n^2}$ covers the full cost. The result is not that the cost has become exactly four copies of ${n^2}$. It is that ${g}$ belongs to the set ${O(n^2)}$.

The number four was not arbitrary, though it was not unique. Look at the piece with the highest power of ${n}$: its coefficient is ${3}$. That coefficient is called the leading coefficient because it belongs to the leading, highest-power piece. The ceiling multiplier must be strictly greater than ${3}$. If we try the boundary value, the extra linear and fixed pieces have nowhere to go:

That can never hold for a positive input. This is the same ${3}$ that the ratio in the earlier lesson approached from above. A multiplier above the leading coefficient clears the extra pieces eventually, and a multiplier at or below it does not.

The controls make the price of the notation visible. A larger multiplier can begin sooner. A multiplier too low has no threshold at all. A valid claim needs both witnesses, not merely a curve that looks convincing over a short range.

Now “eventually” has an exact meaning: for every input at least ${n_0}$. A statement such as ${g \in O(n^2)}$ is therefore a ceiling with a receipt attached, the multiplier and threshold that certify it. This lesson has built only that ceiling. It has not said how slowly the cost can grow, which is the question behind the Upper, lower, and tight door.