2
$\begingroup$

In the big O section of Cracking the Coding Interview 6th edition, I read the following.

"Best, worse, and expected case describe the big O for expected inputs and scenarios."

"Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."

I understand what best, worse, and the expected case is describing.

I know what bounds are but still don't understand the decoupling of the two concepts. Why would an algorithm have different bounds if the inputs/scenarios are the same?

Thanks in advance!

$\endgroup$
3
$\begingroup$

Why would an algorithm have different bounds if the inputs/scenarios are the same?

A deterministic algorithm has a single running time on each input. However, this is not what best case, worst case and average case are about. Let us consider a deterministic sorting algorithm. Its running time on an array of length $n$ depends on the array (and on the algorithm). The best case running time is the minimal running time of the algorithm on an array of length $n$. The worst case running time is the maximal running time of the algorithm on an array of length $n$. The average case running time with respect to a distribution on arrays of length $n$ is the average running time of the algorithm on an array chosen at random from the given distribution.

For a randomized algorithm, it makes sense to consider the best case, worst case and average case for a single input, but this is not what these terms usually refer to.

"Best, worse, and expected case describe the big O for expected inputs and scenarios."

This is simply wrong. I have explained above the meaning of best case, worst case and average case running time for the particular case of sorting algorithms, and the general case is similar.

How is running time measured? One way to measure running time is via an experiment – choose an actual machine, code the algorithm in a particular way, and measure the running time. However, this approach is problematic – which machine should we run the code on? How should we implement the algorithm? Another problem that the exact formula for the running time might be very complicated, and so not very helpful.

The way out is to state the running time up to a constant factor. This makes sense since under reasonable assumptions, the exact machine used and the exact implementation only affect the running time by a constant factor. Moreover, this allows us to hide the complexities of the exact running time by sweeping them under the rug of asymptotic notation. (As an aside, we measure the running time on an abstract machine known as the RAM machine, which has unbounded memory. This allows us to make sense of arbitrary input sizes.)

Consequently, we always quote the running time in asymptotic notation. It is common to use big O notation, but this is in fact only an upper bound on the running time. Merge sort, for example, runs in time $O(n^5)$. It also runs in time $O(n\log n)$, and this upper bound is tight, in the sense that the worst case running time is $\Theta(n\log n)$. When quoting the running time as $O(f(n))$, what one usually means is that the worst case running time is $\Theta(f(n))$. The reason we use big O rather than big $\Theta$ is that on some inputs the algorithm may run faster, and so for arbitrary inputs it may not be correct that the running time is $\Theta(f(n))$, but it is always correct that the running time is upper-bounded by $O(f(n))$.

"Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."

Big O, big $\Omega$ and big $\Theta$ are general-purpose asymptotic notation. They can be used to express asymptotic estimates on the rate of growth of arbitrary functions. Even in computer science, it is common to use asymptotic notation not only to measure running time, but also to measure memory consumption; and in other fields asymptotic notation is used for functions not related to algorithms at all.

$\endgroup$