Editing Amortized analysis (section)

==Method==
{{main|Accounting method (computer science)|Potential method}}
Amortized analysis requires knowledge of which series of operations are possible. This is most commonly the case with [[data structure]]s, which have [[state (computer science)|state]] that persists between operations. The basic idea is that a worst-case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

There are generally three methods for performing amortized analysis: the aggregate method, the [[accounting method (computer science)|accounting method]], and the [[potential method]]. All of these give correct answers; the choice of which to use depends on which is most convenient for a particular situation.<ref name="Lecture 20">{{cite web|url=http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm|title=CS 3110 Lecture 20: Amortized Analysis|last=Kozen|first=Dexter|date=Spring 2011|publisher=[[Cornell University]]|access-date=14 March 2015}}</ref>

*Aggregate analysis determines the upper bound ''T''(''n'') on the total cost of a sequence of ''n'' operations, then calculates the amortized cost to be ''T''(''n'') / ''n''.<ref name="Lecture 20"/>
*The [[accounting method (computer science)|accounting method]] is a form of aggregate analysis which assigns to each operation an ''amortized cost'' which may differ from its actual cost.  Early operations have an amortized cost higher than their actual cost, which accumulates a saved "credit" that pays for later operations having an amortized cost lower than their actual cost.  Because the credit begins at zero, the actual cost of a sequence of operations equals the amortized cost minus the accumulated credit.  Because the credit is required to be non-negative, the amortized cost is an upper bound on the actual cost.  Usually, many short-running operations accumulate such credit in small increments, while rare long-running operations decrease it drastically.<ref name="Lecture 20"/>
*The [[potential method]] is a form of the accounting method where the saved credit is computed as a function (the "potential") of the state of the data structure.  The amortized cost is the immediate cost plus the change in potential.<ref name="Lecture 20"/>