Potential method

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.

The method

The potential function $phi$ 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 "i"th 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\; +\; phi(A\_i)\; -\; phi(A\_\{i-1\})$ (i.e., the effective cost is the actual cost plus the difference in potential).

If $phi$ 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.

Sample applications

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.

See also

* Amortized analysis
* Fibonacci heaps

External links

* [http://www.cs.utexas.edu/~vlr/s06.357/notes/lec16.pdf Amortized analysis in the University of Texas]