For many algorithms, it is important to analyze average performance as well as worstcase 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...j1] 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 worsecase running time.
Average performance and worstcase performance are the most used in algorithm analysis while bestcase 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.
Search Encyclopedia

Featured Article
