Java Reference
In-Depth Information
3.2
Best, Worst, and Average Cases
Consider the problem of finding the factorial of n. For this problem, there is only
one input of a given “size” (that is, there is only a single instance for each size of
n). Now consider our largest-value sequential search algorithm of Example 3.1,
which always examines every array value. This algorithm works on many inputs of
a given size n. That is, there are many possible arrays of any given size. However,
no matter what array of size n that the algorithm looks at, its cost will always be
the same in that it always looks at every element in the array one time.
For some algorithms, different inputs of a given size require different amounts
of time. For example, consider the problem of searching an array containing n
integers to find the one with a particular value K (assume that K appears exactly
once in the array). The sequential search algorithm begins at the first position in
the array and looks at each value in turn until K is found. Once K is found, the
algorithm stops. This is different from the largest-value sequential search algorithm
of Example 3.1, which always examines every array value.
There is a wide range of possible running times for the sequential search alg-
orithm. The first integer in the array could have value K, and so only one integer
is examined. In this case the running time is short. This is the best case for this
algorithm, because it is not possible for sequential search to look at less than one
value. Alternatively, if the last position in the array contains K, then the running
time is relatively long, because the algorithm must examine n values. This is the
worst case for this algorithm, because sequential search never looks at more than
n values. If we implement sequential search as a program and run it many times
on many different arrays of size n, or search for many different values of K within
the same array, we expect the algorithm on average to go halfway through the array
before finding the value we seek. On average, the algorithm examines about n=2
values. We call this the average case for this algorithm.
When analyzing an algorithm, should we study the best, worst, or average case?
Normally we are not interested in the best case, because this might happen only
rarely and generally is too optimistic for a fair characterization of the algorithm's
running time. In other words, analysis based on the best case is not likely to be
representative of the behavior of the algorithm. However, there are rare instances
where a best-case analysis is useful — in particular, when the best case has high
probability of occurring. In Chapter 7 you will see some examples where taking
advantage of the best-case running time for one sorting algorithm makes a second
more efficient.
How about the worst case? The advantage to analyzing the worst case is that
you know for certain that the algorithm must perform at least that well. This is es-
pecially important for real-time applications, such as for the computers that monitor
an air traffic control system. Here, it would not be acceptable to use an algorithm
