Editing Best, worst and average case (section)

== Worst-case versus amortized versus average-case performance ==
{{unreferenced section|date=September 2017}}

{{see|average-case complexity|amortized analysis|worst-case complexity}}

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

Determining what ''typical 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 [[string (computer science)|string]]s 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 analysis of equations.<ref>{{Citation | last1 = Spielman | first1 = Daniel | author-link = Daniel Spielman | last2 = Teng | first2 = Shang-Hua | author2-link = Shangua Teng | journal = Communications of the ACM | publisher = ACM | volume = 52 | issue = 10  | year = 2009 | title = Smoothed analysis: an attempt to explain the behavior of algorithms in practice | page = 76-84 | url = http://cs-www.cs.yale.edu/homes/spielman/Research/cacmSmooth.pdf | doi = 10.1145/1562764.1562785| s2cid = 7904807 }}</ref>

Worst-case analysis gives a ''safe'' analysis (the worst case is never underestimated), but one which can be overly ''pessimistic'', since there may be no (realistic) input that would take this many steps.

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. One modern approach in academic theory to bridge the gap between worst-case and average-case analysis is called [[smoothed analysis]].

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 [[Operation (mathematics)|operations]]. This '''amortized''' cost can be much closer to the average cost, while still providing a guaranteed upper limit on the running time. So e.g. [[online algorithm]]s are frequently based on amortized analysis.

The worst-case analysis is related to the [[worst-case complexity]].<ref>{{Cite web |url=http://www.fsz.bme.hu/~szirmay/ray6.pdf |title=Worst-case complexity |access-date=2008-11-30 |archive-url=https://web.archive.org/web/20110721103906/http://www.fsz.bme.hu/~szirmay/ray6.pdf |archive-date=2011-07-21 |url-status=live }}</ref>