Best and worst cases
|
|
In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. An algorithm's average performance is its behavior under "normal conditions". In almost all situations the resource being considered is running time, but it could also be memory, for instance. The worst case is most of concern since it is of critical importance to know how much time would be needed to guarantee the algorithm would finish.
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.
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.
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 tj = 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(n2) (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.
See also
- Sorting algorithm - an area where there is a great deal of performance analysis of various algorithms.de:Zeitkomplexität