Maths/Big O notation

Sets and membership

After thiswhat you will be able to doRead T in O(n squared) as a membership claim, compare growth classes by subset, and show why an upper bound can be true but loose.

Questionwhat this lesson answersThe O(f) lesson called O of n squared a set of functions and wrote that a cost belongs to it, leaning on the words set and belongs as if they were obvious. What is a set, what is it for a thing to belong to one, and why do the growth classes nest inside each other?

Not coveredwhat this lesson leaves outWe build the set machinery the O(f) lesson assumed and show the growth classes nesting. We do not develop the axioms of set theory, and we do not count how many functions a class contains.

The What O(f) actually is lesson made a move that was easy to read past. It called ${O(n^2)}$ a set of functions and wrote that a cost belongs to it. Those words did real work, but the lesson was busy earning a different claim: the two witnesses that make an upper-bound test true. What is the collection here? What is one thing inside it? What does it mean to say that a cost passes from outside to inside?

Start with an ordinary act of sorting. You put several things behind one label and decide, with a rule, which things count. A collection treated as one object in that way is called a set. The rule is not optional. A bag of names on a page becomes a mathematical set only when there is a definite answer to the question, “does this thing count?”

One thing selected by that rule is called an element. The relation between one element and the set that contains it is called membership. The belongs-to sign is ${\in}$. A short claim such as ${T \in O(n^2)}$ says that the cost rule ${T}$ is one of the functions selected by the rule for ${O(n^2)}$. It is not loose talk about a cost being roughly nearby. It says the cost passes a particular test.

A compact notation makes the rule visible. Begin with possible things called ${x}$, then keep the ones for which a stated condition is true. This way of writing a rule is called set-builder notation:

Read it as “the x such that the condition holds.” The braces make one collection. The part after the colon is its gatekeeper. Change the condition and you have changed the set, even if the same letter appears before the colon.

That is exactly the structure hidden in the earlier upper-bound definition. Its set starts with possible cost functions and keeps the ones for which two witness numbers make the ceiling hold from some threshold onward. Writing

means checking ${T}$ against that condition. The multiplier and starting input built in the What O(f) actually is lesson are the witnesses for this membership test. “Belongs to” is therefore a claim with a receipt, not a vague replacement for an equals sign.

One collection inside another

Now compare two collections. Suppose every thing admitted by the first rule is also admitted by the second. The first collection sits wholly inside the second. A set in that position is called a subset, written with a contained-in sign:

The sign says that every element of ${A}$ is also an element of ${B}$. It does not say the two sets have exactly the same elements. If the second one has at least one extra element, the first sits strictly inside it. That stronger kind of containment is called a proper subset, and its sign is the contained-in sign crossed by a stroke, ${\subsetneq}$.

The growth classes from the arc have this structure. Take a cost with a straight-line ceiling, meaning one that is at most a fixed multiple of ${n}$. The same multiplier also makes a square ceiling work once the input is at least one, because

So every function in ${O(n)}$ is also in ${O(n^2)}$. The first class is a subset of the second. The same move repeats along the familiar family of ceilings:

Read the chain from left to right, each shape fitting beneath the next ceiling. A fixed amount is eventually below any multiple of a repeated-cut count. That repeated-cut count is eventually below a straight line. A straight line fits beneath one straight-line pass on each repeated-cut level. That combined ceiling fits beneath a square, and a square fits beneath a cube. At each step the ceiling on the right grows faster, so it can cover every function already covered by the slower ceiling on the left. The definition of ${O(\ldots)}$ gives each statement room to choose a threshold and a fixed multiplier.

Every containment shown is proper. The function ${n^2}$ belongs to ${O(n^2)}$, but it cannot belong to ${O(n)}$. No matter which fixed multiplier ${c}$ is chosen, the square passes its straight-line ceiling once the input is larger than that multiplier:

The same kind of counterexample separates every neighboring pair: a repeated-cut count is not fixed, a straight line is not bounded by repeated cuts, and so on. The boxes are genuinely getting bigger, not merely acquiring different names.

This nesting explains why an upper bound can be true and still unhelpful. Saying a cost is ${O(n^2)}$ also says something true about any cost that lives in ${O(n)}$, ${O(\log n)}$, or ${O(1)}$. It supplies a ceiling, but it may leave a great deal of empty space above the cost.

For a cost that matches one of these named shapes, the smallest class in the chain is the useful one. Calling that rate tight means no smaller class in this displayed chain still contains the cost. The Upper, lower, and tight door gives that idea its full two-sided test, with a floor as well as a ceiling. Here the point is simpler: a loose upper bound is possible because classes are sets, and these sets nest.