Best, worst and average case

Best, worst and average case

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 resource.

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 would 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 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 running times.

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, a simple linear search on an array has a worst-case performance O(n) (for the case where the desired element is the last, so the algorithm has to check every element; see Big O notation), and average running time is O(n) (the average position of an element is the middle of the array, ie. at position n/2, and O(n/2)=O(n)), but in the best case the desired element is the first element in the array and the run time is O(1).

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 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.

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.

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.

Practical consequences

Many problems with bad worst-case performance have good average-case performance. For problems we want to solve, this is a good thing: we can hope that the particular instances we care about are average. For cryptography, this is very bad: we want typical instances of a cryptographic problem to be hard. Here methods like random self-reducibility can be used for some specific problems to show that the worst case is no harder than the average case, or, equivalently, that the average case is no easier than the worst case.

Examples

* In the worst case, linear search on an array must visit every element once. It does this if either the element being sought is the last element in the list, or if the element being sought is not in the list. However, on average, assuming the input is in the list, it visits only "n"/2 elements.

* Applying insertion sort on "n" elements. On average, half the elements in an array "A"1 ... A"j"-1 are less than an element Aj, 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 worst-case running time.

* The popular sorting algorithm Quicksort has an average case performance of O(n log n), which contributes to making it a very fast algorithm in practice. But given a worst-case input, its performance can degrade to O("n"2).

ee also

* Sorting algorithm - an area where there is a great deal of performance analysis of various algorithms.
* Worst case circuit analysis


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Worst-case scenario — is a situation where everything that can go wrong, does go wrong.It is also used to refer to:* Worst Case Scenarios (TV series), a reality show aired on TBS in 2002 in the U.S. * Worst Case Scenario , 1994 album by dEUS * , episode of Star Trek:… …   Wikipedia

  • Business and Industry Review — ▪ 1999 Introduction Overview        Annual Average Rates of Growth of Manufacturing Output, 1980 97, Table Pattern of Output, 1994 97, Table Index Numbers of Production, Employment, and Productivity in Manufacturing Industries, Table (For Annual… …   Universalium

  • Media and Publishing — ▪ 2007 Introduction The Frankfurt Book Fair enjoyed a record number of exhibitors, and the distribution of free newspapers surged. TV broadcasters experimented with ways of engaging their audience via the Internet; mobile TV grew; magazine… …   Universalium

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Agriculture and Food Supplies — ▪ 2007 Introduction Bird flu reached Europe and Africa, and concerns over BSE continued to disrupt trade in beef. An international vault for seeds was under construction on an Arctic island. Stocks of important food fish species were reported… …   Universalium

  • Computers and Information Systems — ▪ 2009 Introduction Smartphone: The New Computer.       The market for the smartphone in reality a handheld computer for Web browsing, e mail, music, and video that was integrated with a cellular telephone continued to grow in 2008. According to… …   Universalium

  • Canada's Worst Driver 3 — Infobox Television show name = Canada s Worst Driver 3 caption = Canada s Worst Driver Logo format = Reality television runtime = 60 minutes creator = developer = Proper Television producer = Blair Ricard executive producer = Guy O Sullivan… …   Wikipedia

  • Major professional sports leagues of the United States and Canada — Major professional sports league, or simply major league, is the term used in Canada and the United States to refer to the highest professional division in any team sport. The term major league was first used in 1921 in reference to Major League… …   Wikipedia

  • Analysis of algorithms — To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or running time of an algorithm is… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”