Maths/Big O notation

Best, worst, and average

After thiswhat you will be able to doClassify the best, worst, and uniform-average costs of a front-to-back search with O, Omega, and Theta without confusing the case with the bound.

Questionwhat this lesson answersTwo earlier lessons said the growth bounds and the choice of input are different axes, and one built the average. So what are the three cases, how does each combine with an upper, lower, or tight bound, and why does asking for "the complexity" of an algorithm have no single answer?

Not coveredwhat this lesson leaves outWe fill the grid of three cases against three bounds for one search, using the average the expectation lesson already computed. We do not survey the cases of any harder algorithm, and we do not prove a lower bound over all algorithms.

Two threads have been running beside each other. The Upper, lower, and tight lesson said that a bound describes how one chosen rule for cost changes as the input gets larger. ${O}$ gives that rule a ceiling, ${\Omega}$ gives it a floor, and ${\Theta}$ says the ceiling and floor fit the same growth shape. That lesson also pointed out that best, worst, and average do something else: they choose which input of a given size supplies the cost. A bound does not make that choice.

The Expectation lesson took the second thread and built one average. Its front-to-back search checks a list from the first item onward. When every target position is chosen uniformly, the weighted average is ${\dfrac{n + 1}{2}}$ comparisons. That calculation belongs behind the Expectation door. Here we take its result as given and place it beside the two extreme cases.

One search, three ways to choose an input

Keep the algorithm concrete. A front-to-back search looks at each item until it reaches the target. Let ${n}$ be the number of items in the list. If the target sits at position ${k}$, the search makes ${k}$ comparisons, because it checks every earlier item and then that position. The target first gives one comparison. The target last gives one comparison for every item.

Choosing the first target is the best case. Choosing the final target is the worst case. Choosing among all positions with the uniform rule gives the average case already computed by expectation. For this one search, the three costs are:

These are not three names for one number. They are three different answers to the question, “which input of size ${n}$ are we measuring?” The average answer needs its uniform assumption. Without that assumption, the search still has a best and a worst cost, but it does not have this particular average.

Choose the case first, then the bound

The central move is an order of questions. First choose a case. That gives one rule that tells us the comparison count for each list size. A rule of that kind is called a cost function. Then put a bound on that chosen function. The case and the bound are independent choices, so they make a grid: rows choose inputs, and columns describe the resulting cost.

Start with the best row. Its cost is the constant ${1}$. It never increases with ${n}$, so it has an upper bound ${O(1)}$ and a lower bound ${\Omega(1)}$. Since both use the same constant shape, the row also has the tight bound ${\Theta(1)}$.

The worst row is just ${n}$. It has an upper bound ${O(n)}$, a lower bound ${\Omega(n)}$, and the tight description ${\Theta(n)}$. The three labels do not compete. They give a ceiling, floor, and tight fit for the same worst-case cost function.

The average row is not constant just because it is smaller than the worst row. Its cost is ${\dfrac{n + 1}{2}}$. Half a list still grows in step with the whole list, which is the linear shape. The two simple inequalities show why both the ceiling and floor use ${n}$:

So the uniform average is ${O(n)}$, ${\Omega(n)}$, and ${\Theta(n)}$. The tight label is available in every row of this example because we know the exact shape of every row’s cost. Another algorithm might leave us with only a ceiling or only a floor until more work is done.

The slider changes the three actual comparison counts, while the table keeps the two axes apart. The best count stays at one. The average stays between the best and worst counts. Its tight shape still matches the worst row’s shape even though its count is smaller at every list size above one.

The missing word in “the complexity”

A compact claim about a program’s cost as its input grows is called a complexity statement. The phrase “the complexity of the search” is not one statement. It needs at least a case and a bound. Someone who says “the search is ${O(n)}$” has often quietly chosen the worst case. The uniform average also has that upper bound. Someone who says “it is ${\Theta(1)}$” has quietly chosen the best case. Neither statement is wrong, but neither identifies the search’s behavior completely without naming its case.

That is why one algorithm carries several honest complexity statements at once. The same front-to-back search is best-case ${\Theta(1)}$, worst-case ${\Theta(n)}$, and uniform-average ${\Theta(n)}$. Saying the case out loud says which cost function the bound is about. Saying the bound says what kind of claim is being made about that cost function.

Worst case and ${O}$ are often spoken together, but they answer different questions. Worst case chooses the input that makes this search work the longest. ${O}$ asks for a ceiling on whichever cost has already been chosen. The grid gives a lower bound ${\Omega(1)}$ on the best case just as easily. The pairing “worst case, O” is a convention, not a law.

There is one final limit to keep visible. A lower bound on this algorithm’s worst case says this algorithm cannot do better than that cost on its worst inputs. It does not say that no algorithm can do better on the same problem. That stronger statement needs a different method, behind the Lower bound proofs door.