Encyclopedia > Average performance

  Article Content

Average performance

The term average performance is used in computer science to describe the way an algorithm behaves 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 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.

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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... at once, a surface level and a semantic (meaningful) level. 'Metalinguistics:' Ability to discuss language itself. 'Productivity:' A finite number of units can b ...