Editing Amortized analysis (section)

{{Short description|Method for algorithm analysis in computer science}}
{{Redirect|Amortized|other uses|Amortization (disambiguation){{!}}Amortization}}
In [[computer science]], '''amortized analysis''' is a method for [[Analysis of algorithms|analyzing]] a given algorithm's [[Computational complexity|complexity]], or how much of a resource, especially time or memory, it takes to [[Execution (computing)|execute]].  The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic.  Instead, amortized analysis averages the running times of operations in a sequence over that sequence.<ref name="tarjan"/>{{rp|306}}
As a conclusion: "Amortized analysis is a useful tool that complements other techniques such as [[Worst-case execution time|worst-case]] and [[Average-case complexity|average-case]] analysis."<ref name="fiebrink"/>{{rp|14}}<ref>{{cite web|quote="[Amortized analysis] is different from what is commonly referred to as average case analysis, because amortized analysis does not make any assumption about the distribution of the data values, whereas average case analysis assumes the data are not "bad" (e.g., some sorting algorithms do well on "average" over all input orderings but very badly on certain input orderings).  That is, amortized analysis is a worst case analysis, but for a sequence of operations, rather than for individual operations." |title=Lecture 18: Amortized Algorithms |work=CS312 -Data Structures and Functional Programming |date=2006 |publisher=Cornell University |url=https://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec18.html }}</ref>

For a given operation of an algorithm, certain situations (e.g., input parametrizations or data structure contents) may imply a significant cost in resources, whereas other situations may not be as costly.  The amortized analysis considers both the costly and less costly operations together over the whole sequence of operations.  This may include accounting for different types of input, length of the input, and other factors that affect its performance.<ref name="fiebrink">{{Citation |url=http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf |title=Amortized Analysis Explained |author=Rebecca Fiebrink |year=2007 |access-date=2011-05-03 |archive-url=https://web.archive.org/web/20131020020356/http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf |archive-date=20 October 2013 |url-status=dead }}</ref>