In computational complexity theory, the potential method is a method used to analyze the amortized time and space complexity of a data structure, a measure of its performance over sequences of operations that smooths out the cost of infrequent but expensive operations.
[1][2] 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.
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.
, define: Then: 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.
Typically, amortized analysis is used in combination with a worst case assumption about the input sequence.
Allocating a new internal array A and copying all of the values from the old internal array to the new one takes O(n) actual time, but (with an appropriate choice of the constant of proportionality C) this is entirely cancelled by the decrease in the potential function, leaving again a constant total amortized time for the operation.
The other operations of the data structure (reading and writing array cells without changing the array size) do not cause the potential function to change and have the same constant amortized time as their actual time.
This structure may be analyzed using the potential function: This number is always non-negative, as required.
This proves that any sequence of m operations takes O(m) actual time in the worst case.
Consider a counter represented as a binary number and supporting the following operations: For this example, we are not using the transdichotomous machine model, but instead require one unit of time per bit operation in the increment.
This structure may be analyzed using the potential function: This number is always non-negative and starts with 0, as required.
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.