Potential method

In Computational complexity theory, the Potential method is a method used to analyze amortized time and space complexities of algorithms. 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

Similar to potential in physics, a potential function is a real valued function from states of the data structure in question. Assume a data structure goes through a series of states $A_{0}\dots A_{n}$ after n different operations, and $\phi$ is a potential function. If $t_{i}$ is the runtime of operation number i, we define its amortized runtime to be $a_{i}=t_{i}+\delta \phi _{i}$.

The total runtime of the n operations equals $\Sigma _{i=1}^{n}a_{i}+\phi _{0}-\phi _{m}$. If $\phi$ satisfies $\phi _{0}-\phi _{m}\leq 0$ then the runtime of all n operations is less or equal the sum of all amortized times.

Example application

The problem of Table expansion can be solved using the potential method. Choose as potential function the number of occupied cells minus the number of vacant cells. Every regular inserts increases the potential by O(1). An insert that causes reallocation decreases the potential by n, which is the exact amount of work done in the reallocation, thus getting O(1) amortized time for insert.

See also

• Amortized analysis

External Links

Amortized analysis in the University of Texas