Best, worst and average case

From Freepedia

In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. In almost all situations the resource being considered is running time, but it could also be memory, for instance. In real-time systems, the worst case execution time is often of particular concern since it important to know how much time might be needed in the worst case to guarantee the algorithm would always finish on time.

Average performance and worst-case performance are the most used in algorithm analysis. Less widely found is best-case performance, but it does have uses, for example knowing the best cases of individual tasks can be used to improve accuracy of an overall worst case analysis. Computer scientists use probabilistic analysis techniques, especially expected value, to determine expected average running times.

Worst case vs average case performance

Worst case performance analysis and average case performance analysis have similarities, but usually require different tools and approaches in practice.

Determining what average input is in itself difficult, and often that average input has properties which make it difficult to characterise mathematically (consider, for instance, algorithms that are designed to operate on strings of text). Similarly, even when a sensible description of a particular "average case" (which will probably only be applicable for some uses of the algorithm) is possible, they tend to result in more difficult to analyse equations.

Worst case analysis has similar problems, typically it is impossible to determine the exact worst case scenario. Instead, longest possible path through the algorithm is considered, which leads to a safe analysis (the worst case is never underestimated), but which is pessimistic, since no input might require this path. A better analysis can provide a tighter upper bound of the worst case scenario for the same algorithm. Alternatively, a scenario which is thought to be close to the real worst case may be considered, which leads to a potentially unsafe result, but one that may be much more practical than one that is too pessimistic.

Examples

• Linear search on an array has a worst-case performance O(n), when the algorithm has to check every element, but the average running time is O(n/2), when the item to be found is around the middle of an array.

• Applying insertion sort on n elements. On average, half the elements in an array A₁ ... A_j-1 are less than an element A_j, and half are greater. Therefore we check half the subarray so t_j = j/2. Working out the resulting average case running time yields a quadratic function of the input size, just like the worse case running time.

• The famous sort algorithm Quicksort, which is, in the average case, a very fast algorithm. But if not used with great care, its worst case performance can degrade to O(n²) (see Big O notation), ironically when the target list is already sorted.

See also

• Sorting algorithm - an area where there is a great deal of performance analysis of various algorithms.