Best, worst and average case

related topics
{math, number, function}
{rate, high, increase}
{system, computer, user}
{theory, work, human}

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. Usually the resource being considered is running time, but it could also be memory or other resources.

In real-time computing, the worst-case execution time is often of particular concern since it is important to know how much time might be needed in the worst case to guarantee that the algorithm will always finish on time.

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, where the best cases of individual tasks are known, they can be used to improve the accuracy of an overall worst-case analysis. Computer scientists use probabilistic analysis techniques, especially expected value, to determine expected running times.

The terms are used in other contexts; for example the worst- and best-case outcome of a planned-for epidemic, worst-case temperature to which an electronic circuit element is exposed, etc. Where components of specified tolerance are used, devices must be designed to work properly with the worst-case combination of tolerances and external conditions.

Contents

Best-case performance

The term best-case performance is used in computer science to describe the way an algorithm behaves under optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.

Development and choice of algorithms is rarely based on best-case performance: most academic and commercial enterprises are more interested in improving average performance and worst-case performance.

Worst-case versus average-case performance

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

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.

Worst-case analysis has similar problems: it is typically impossible to determine the exact worst-case scenario. Instead, a scenario is considered such that it 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 the maximum number of loops, for instance) even if it is not possible to determine the exact input that would generate this path (indeed, such an input may not exist). This gives a safe analysis (the worst case is never underestimated), but one which is pessimistic, since there may be no input that would require this path.

Full article ▸

related documents
Kolmogorov-Smirnov test
Median
Log-normal distribution
Quantile
Cauchy distribution
Weighted mean
Whittaker–Shannon interpolation formula
Pareto distribution
Range encoding
Box-Muller transform
Heaviside step function
Separated sets
Magma (algebra)
Twin prime conjecture
Topological ring
Polynomial time
Goldbach's weak conjecture
Kernel (category theory)
Intersection (set theory)
NP-hard
Greedy algorithm
Euler's criterion
Graded algebra
Lipschitz continuity
Partial fractions in integration
Regular space
Real line
Complement (set theory)
Divisor
Simple LR parser