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
Tax, tariff and trade

... or discourage imports or consumption inside the jurisdiction. Trade, especially investment, policy to encourage or discourage location of particular types of ...