Best, worst and average case

The term worst-case performance is used to describe the way an algorithm behaves under conditions that cause its performance to be as poor as possible. For example, a simple linear search has an average running time of O(n/2) (see Big O notation), but a worst case performance O(n), when the item to be found is the last item in the table.

For many algorithms, it is important to analyze worst-case performance as well as average performance. A classic example is Quicksort, which is, in the average case, a very fast algorithm. But if not implemented with great care, its worst-case performance can degrade to O(n²), ironically when the target table is already sorted.