Run-Times: Bounds vs Case

Question

Note: Please do not tag this as homework! I am not a student and this is not an assignment. I am a software engineer dusting off my old Data Structures & Algorithms textbook and trying to remember stuff I learned years ago and that I cannot seem to find anywhere online.

I recall a specific lecture, and it is reinforced in my textbook, that algorithm bounds (upper, tight and lower) and cases (best, average and worst) are not one in the same. But for the life of me I can't remember how the two concepts are different.

To me, if some algorithm is O(n) worst-case, then it can perform any worse than some linear function, such as f(n) = cn + k. Since we are guaranteed this in the worst case, it seems to me that its upper-bound is also linear.

I know I'm wrong, I just can't figure out why.

I'm a contextual learner, so if someone could provide a meaningful example where either worst-case is not upper bound, or best case is not lower bound, or where average case is not tight-bound, that would probably get through to me the fastest.

Thanks for any clarity on this!

Answer 1

Consider a variant of quicksort that checks if the array is already sorted and, if not, sorts using the first element as a pivot.

The best case is O(n) if the array is already sorted. This is an upper bound on the best-case behavior, which is meaningful if not interesting.

The average case over random inputs is O(n^3/2) and Ω(n). Okay, I cheated slighty because it's also Theta(n log n), but the idea is that bounds are not always tight, and this lack of tightness may manifest itself when I'm describing average-case bounds.

The worst case is Theta(n²) if the array is reverse sorted, because the subproblems are so unbalanced (each time, we pivot with the maximum element, resulting in subproblems of sizes 0 and n - 1 instead of about n/2 and about n/2). This is a tight bound on the worst case and shows that the algorithm really can be that bad, but no worse. Quicksort is also O(n³), but not Theta(n³), because quicksort has no family of inputs that results in cubic behavior.

Answer 2

The case refers to the type of running time being investigated, whereas the bound refers to a function for that running time.

Saying that an algorithm has worst-case running time of O(f(n)) is equivalent to saying that f(n) is an asymptotic upper bound for the worst-case running time of the algorithm.

The 3 cases (best-case, average-case, and worst-case) and 5 asymptotic bounds (upper (O), tight upper (o), lower (Ω), tight lower (ω), and tight (Θ)) give 15 distinct ways of making a statement about the running time.

Confusion or disaster can arise if the bound is specified without the case. For example the lower bound of a sorting algorithm can be both Θ(n) and Θ(n lg n), depending on whether we are talking about best-case or worst-case. A Θ(1) average case running time is no good if the Θ(n³) worst-case running time makes the factory grind to a halt.