Maths/Big O notation

Upper, lower, and tight

After thiswhat you will be able to doBuild upper, lower, and tight bounds with multipliers and thresholds, and keep those bounds separate from best, worst, and average inputs.

Questionwhat this lesson answersO(f) only promises a cost grows no faster than f. What says it grows no slower, what says it grows at exactly the rate of f, and why is none of that the same question as best case versus worst case?

Not coveredwhat this lesson leaves outWe define the lower bound and the tight bound by mirroring the upper one, and we show the running polynomial sits at exactly n squared. We prove no specific lower bound from scratch, and we hold best, worst and average case for the lesson on recurrence relations.

The lesson on what O(f) actually is gave a cost a ceiling: a fixed multiple of another rule used for comparison, called a comparison rule, that stays above the cost once the input is large enough. That is what ${O(f)}$ says. Its full membership test, and the two witnesses it asks you to produce, live behind the What O(f) actually is door. A ceiling of this kind is called an upper bound. It answers only half of the question. A very low cost can sit below it too.

Imagine putting a second line under the cost. This line is also a fixed multiple of the same comparison rule, but the cost must stay above it after some starting input. That lower line is a floor. A floor of this kind is called a lower bound. The collection of functions with such a floor is called ${\Omega(f)}$, read “Omega of f”. Its definition reverses the direction of the final comparison:

The same two kinds of witness appear. A positive multiplier sets the floor’s height, and a threshold says where the floor must remain below the cost. This lower statement is about one cost rule. It is not yet a claim that every possible algorithm must do at least this much work. The harder claim is what the Lower bound proofs door is for.

Put a ceiling and a floor around the cost, both made from the same comparison rule. If the cost cannot escape above the first or below the second after one shared starting point, its rate has been pinned from both sides. A two-sided bound of this kind is called a tight bound. Its symbol is ${\Theta(f)}$, read “Theta of f”. It means membership in both collections:

The word tight describes the fit between the two multiples. It does not say the two curves touch, or that either multiple is unique. It says they have the same comparison shape and trap the cost between them for all sufficiently large inputs.

The running cost between two curves

Use the familiar comparison rule ${f(n) = n^2}$ and the familiar cost rule:

For the ceiling, the lesson on what O(f) actually is already found the first witness pair. Give the ceiling multiplier the name ${c_1}$. With ${c_1 = 4}$, the cost stays at or below four copies of ${n^2}$ from input ${538}$ onward:

For the floor, give its multiplier the name ${c_2}$. Choose ${c_2 = 3}$. The extra linear and fixed pieces are positive for every positive input, so the floor works immediately:

The two statements can share the later threshold. From ${538}$ onward the cost is enclosed:

That gives a ceiling witness ${c_1 = 4}$ with threshold ${538}$, and a floor witness ${c_2 = 3}$ with threshold ${1}$. Since both comparison shapes are ${n^2}$, the cost belongs to ${\Theta(n^2)}$. The floor is easy in this example because the discarded pieces are positive. The ceiling has to wait for them to become small compared with the quadratic piece.

The island also shows why a tighter ceiling can require more patience. Move its ceiling multiplier closer to the coefficient on the highest-power piece, the leading coefficient. The gap around the cost narrows, but the threshold moves to a larger input. A tight bound is not a claim that you found the closest possible lines. It is the claim that some fixed pair works.

A different question from cases

There is a separate source of confusion. The symbols ${O}$, ${\Omega}$, and ${\Theta}$ describe how one chosen cost function, a rule that assigns a step count to each input size, changes as the input grows. They do not choose which input a program receives. For a fixed size, some inputs can let a program stop quickly and others can make it keep working. The input that gives the fewest steps is called a best-case input. The one that gives the most steps is called a worst-case input. An average-case cost takes an average over inputs, which also requires saying how likely each possible input is.

These are separate questions, or separate axes of description. You can ask for an upper bound on the best-case cost, a lower bound on the worst-case cost, or any other pairing. Hearing “worst case” should not make you think ${O}$, and hearing “best case” should not make you think ${\Omega}$. The first pair of words chooses an input from a size class. The second pair compares the resulting cost rule with a growth shape.

Consider a program that checks a list whose items have no order, called an unsorted list, from the first item onward until it finds a target. When the target is first, it makes one check. Its best-case cost is ${O(1)}$, and it also has the matching lower statement ${\Omega(1)}$. When the target is last, it makes one check for each item. Its worst-case cost is ${O(n)}$, and it also has the matching lower statement ${\Omega(n)}$. The two facts use both axes at once without identifying them. The Best, worst, and average door untangles the cases fully.

When you can show both walls around a chosen cost, ${\Theta}$ is the honest description of its rate. ${O}$ alone is only a ceiling, and it might be loose. The upper-bound definition is behind the earlier door; the next door takes up the input choices that bounds do not make for you.