Home > Best and worst cases

Average performance and worst-case performance are the most used in algorithm analysis while best-case performance is more of a fantasy description of an algorithm. Computer scientists use probabilistic analysis techniques, especially expected value, to determine expected average running times

1 Worst case vs average case performance

Worst case performance analysis is often easier to do than "average case" performance. 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.

2 Examples

• Applying insertion sort on n elements. On average, half the elements in an array A[1...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.

• 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.

3 See also

• sort algorithm - an area where there is a great deal of performance analysis of various algorithms.
• average performance
• amortized cost