For many algorithms, it is important to analyze average performance as well as worst-case performance. The average case is almost as bad as the worst case in some situations. An example would be to choose n numbers and apply insertion sort. 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.

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

See: sort algorithm - an area where there is a great deal of performance analysis of various algorithms.