Potential method

In the potential method, a function Φ is chosen that maps states of the data structure to non-negative numbers. If S is a state of the data structure, Φ(S) represents work that has been accounted for ("paid for") in the amortized analysis but not yet performed. Thus, Φ(S) may be thought of as calculating the amount of potential energy stored in that state.[1][2] The potential value prior to the operation of initializing a data structure is defined to be zero. Alternatively, Φ(S) may be thought of as representing the amount of disorder in state S or its distance from an ideal state.

Let o be any individual operation within a sequence of operations on some data structure, with S_before denoting the state of the data structure prior to operation o and S_after denoting its state after operation o has completed. Once Φ has been chosen, the amortized time for operation o is defined to be

${\displaystyle T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+C\cdot (\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} })),}$

where C is a non-negative constant of proportionality (in units of time) that must remain fixed throughout the analysis. That is, the amortized time is defined to be the actual time taken by the operation plus C times the difference in potential caused by the operation.[1][2]

When studying asymptotic computational complexity using big O notation, constant factors are irrelevant and so the constant C is usually omitted.

Despite its artificial appearance, the total amortized time of a sequence of operations provides a valid upper bound on the actual time for the same sequence of operations.

For any sequence of operations ${\displaystyle O=o_{1},o_{2},\dots ,o_{n}}$, define:

• The total amortized time: ${\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}T_{\mathrm {amortized} }(o_{i}),}$
• The total actual time: ${\displaystyle T_{\mathrm {actual} }(O)=\sum _{i=1}^{n}T_{\mathrm {actual} }(o_{i}).}$

Then:

${\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual} }(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)=T_{\mathrm {actual} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),}$

where the sequence of potential function values forms a telescoping series in which all terms other than the initial and final potential function values cancel in pairs. Rearranging this, we obtain:

${\displaystyle T_{\mathrm {actual} }(O)=T_{\mathrm {amortized} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).}$

Since ${\displaystyle \Phi (S_{0})=0}$ and ${\displaystyle \Phi (S_{n})\geq 0}$, ${\displaystyle T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)}$, so the amortized time can be used to provide an accurate upper bound on the actual time of a sequence of operations, even though the amortized time for an individual operation may vary widely from its actual time.

Typically, amortized analysis is used in combination with a worst case assumption about the input sequence. With this assumption, if X is a type of operation that may be performed by the data structure, and n is an integer defining the size of the given data structure (for instance, the number of items that it contains), then the amortized time for operations of type X is defined to be the maximum, among all possible sequences of operations on data structures of size n and all operations o_i of type X within the sequence, of the amortized time for operation o_i.

With this definition, the time to perform a sequence of operations may be estimated by multiplying the amortized time for each type of operation in the sequence by the number of operations of that type.

The potential function method is commonly used to analyze Fibonacci heaps, a form of priority queue in which removing an item takes logarithmic amortized time, and all other operations take constant amortized time.[4] It may also be used to analyze splay trees, a self-adjusting form of binary search tree with logarithmic amortized time per operation.[5]