Editing Amortized analysis (section)

==History==
Amortized analysis initially emerged from a method called aggregate analysis, which is now subsumed by amortized analysis. The technique was first formally introduced by [[Robert Tarjan]] in his 1985 paper ''Amortized Computational Complexity'',<ref name="tarjan">{{cite journal
 |last=Tarjan
 |first=Robert Endre
 |author-link=Robert Tarjan
 |title=Amortized Computational Complexity
 |journal=SIAM Journal on Algebraic and Discrete Methods
 |date=April 1985
 |volume=6
 |issue=2
 |pages=306–318
 |doi=10.1137/0606031
 |url=http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf
 |url-status=live
 |access-date=2024-06-09
 |archive-url=https://web.archive.org/web/20150226051958/http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf
 |archive-date=2015-02-26
}}<!--was:http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/Amortized.pdf--></ref> which addressed the need for a more useful form of analysis than the common probabilistic methods used. Amortization was initially used for very specific types of algorithms, particularly those involving [[binary tree]]s and [[Union-find data structure|union]] operations. However, it is now ubiquitous and comes into play when analyzing many other algorithms as well.<ref name="fiebrink"/>