In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. In almost all situations the resource being considered is running time, but it could also be memory, for instance. In real-time systems, the worst case execution time is often of particular concern since it important to know how much time might be needed in the worst case to guarantee the algorithm would always finish on time. Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Flowcharts are often used to represent algorithms. ... It has been suggested that this article or section be merged into Real-time. ... The worst case execution time (WCET) of a computational task is the maximum time span a task may execute on a specific hardware platform. ...

Average performance and worst-case performance are the most used in algorithm analysis. Less widely found is best-case performance, but it does have uses, for example knowing the best cases of individual tasks can be used to improve accuracy of an overall worst case analysis. Computer scientists use probabilistic analysis techniques, especially expected value, to determine expected average running times. The term best-case performance is used in computer science to describe the way an algorithm behaves under optimal conditions. ... Computer science (informally: CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ... The word probability derives from the Latin probare (to prove, or to test). ... In probability theory (and especially gambling), the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects to win per bet if bets with identical...

Worst case versus average case performance

Worst case performance analysis and average case performance analysis have similarities, but usually require different tools and approaches in practice.

Determining what average input means is difficult, and often that average input has properties which make it difficult to characterise mathematically (consider, for instance, algorithms that are designed to operate on strings of text). Similarly, even when a sensible description of a particular "average case" (which will probably only be applicable for some uses of the algorithm) is possible, they tend to result in more difficult to analyse equations. The term input has a variety of uses in different fields. ... In computer programming and some branches of mathematics, strings are sequences of various simple objects. ...

Worst case analysis has similar problems, typically it is impossible to determine the exact worst case scenario. Instead, a scenario is considered which is at least as bad as the worst case. For example, when analysing an algorithm, it may be possible to find the longest possible path through the algorithm (by considering maximum number of loops, for instance) even if it is not possible to determine the exact input that could generate this. Indeed, such an input may not exist. This leads to a safe analysis (the worst case is never underestimated), but which is pessimistic, since no input might require this path. Look up path in Wiktionary, the free dictionary. ... In computer science and in computer programming, statements in pseudocode or in a program are normally obeyed one after the other in the order in which they are written (sequential flow of control). ...

Alternatively, a scenario which is thought to be close to (but not necessarily worse than) the real worst case may be considered. This may lead to an optimistic result, meaning that the analysis may actually underestimate the true worst case.

In some situations it may be necessary to use a pessimistic analysis in order to guarantee safety. Often however, a pessimistic analysis may be too pessimistic, so an analysis that gets closer to the real value but may be optimistic (perhaps with some known low probability of failure) can be a much more practical approach.

When analyzing algorithms which often take a small time to complete, but periodically require a much larger time, amortized analysis can be used to determine the worst case running time over a (possibly infinite) series of operations. This amortized worst case cost can be much closer to the average case cost, while still providing a guaranteed upper limit on the running time. In computational complexity theory, amortized analysis is the time per operation averaged over a worst_case sequence of operations. ... Operations is that unit (be it a division or department) of an organization that carries out the actual execution of the core operating functions. ...

Examples

• Linear search on an array has a worst-case performance O(n) (see Big O notation), because in the worst case, the algorithm has to check every element. However, the average running time is O(n/2).

• Applying insertion sort on n elements. On average, half the elements in an array A₁ ... A_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.

• The famous sort algorithm Quicksort, which is, in the average case, a very fast algorithm. But if not used with great care, its worst case performance can degrade to O(n²), ironically when the target list is already sorted.

It has been suggested that Landau notation be merged into this article or section. ... Insertion sort is a simple sort algorithm in which the sorted array (or list) is built one entry at a time. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Quicksort in action on a list of random numbers. ...

See also

• Sorting algorithm - an area where there is a great deal of performance analysis of various algorithms.