Potential method

From Wikipedia, the free encyclopedia

In algorithms, the potential method is a method used to analyze the amortized time and space complexity of an algorithm. It can be thought of as a generalization of the accounting method and the debit method. It is useful in cases where it is hard to assign credit to specific elements of the structure.

1 The method
2 Sample applications
- 2.1 Table expansion
3 See also
4 External links

[edit] The method

The potential function $φ$ is set to be a positive-valued function from states of the data structure in question. If $c i$ represents the actual cost of the ith operation, which updates the data structure from state $A i - 1$ to state $A i$ , then the effective cost $d i$ of this operation is defined to be $d i = c i + φ(A i) - φ(A i - 1)$ (i.e., the effective cost is the actual cost plus the difference in potential).

If $φ$ is chosen so that the starting state of the data structure has potential 0, then the sum of the effective costs $d_1,\dots,d_n$ is greater than or equal to the sum of the actual costs $c_1,\dots,c_n$ . So if an upper bound on the effective cost of each operation can be shown, this implies an upper bound on the total cost of $n$ operations, which gives an upper bound on the amortized cost per operation.

[edit] Sample applications

[edit] Table expansion

Determining the amortized cost of table expansion can be solved using the potential method. Let the potential function be the number of occupied cells minus the number of vacant cells. A regular insert incurs O(1) cost and increases the potential by O(1); thus, the effective cost of a regular insert is O(1). An insert that causes reallocation incurs cost O(n) but decreases the potential by O(n), giving an effective cost of O(1) for this operation. Since each type of operation has O(1) effective cost, this implies an amortized cost of O(1) as well.