Bounds and Cases Are Different Questions

A case and a bound answer different questions. A case, such as best, worst or average, picks which inputs you are costing, and so picks one cost function. A bound, O, Ω or Θ, says how fast that function grows. This card separates the two using linear search, and shows that any case can carry any bound.

Two engineers review a linear search, a loop that checks each item in turn until it finds the target. One says it is O(n). The other says it is Ω(1), read "big omega of one", and they think they disagree, but each has left something unsaid: which case, and which kind of bound.

On a list of eight distinct items, a run counted the comparisons. With the target first, the search makes one. With the target last, or missing, it makes eight. Averaged over every position the target could hold, it makes 4.5, which is (n + 1)/2.

Each case is a separate function of n. The bounds then describe how each function grows, compared with a simpler function f, such as n or n².

The table applies all three bounds to each of linear search's cases.

So a full cost claim names a case, then a bound: linear search is Θ(n) in the worst case and Θ(1) in the best. An upper bound can also be loose. The worst case is O(n²) as well, since n grows no faster than n², but that statement throws information away. When people write O, they usually mean the tightest upper bound they know.

O, Ω and Θ are not nicknames for worst, best and average. Reading Ω as "the best case" is the usual mix-up, yet the best case of linear search has an O, and its worst case has an Ω.

Every cost in the rest of this subject names its case, because one operation can be O(1) for some inputs and O(n) for others. Read the case first and the bound second, and you know which promise a cost makes.