Average performance

In computer science, an algorithm's average performance is its behavior under normal conditions. For example, a simple 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) (see Big O notation), when the item to be found is around the middle of an array.

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.