- 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 thedebit 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 heap sExternal links
* [http://www.cs.utexas.edu/~vlr/s06.357/notes/lec16.pdf Amortized analysis in the University of Texas]
Wikimedia Foundation. 2010.