Potential method

From Wikipedia, the free encyclopedia

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.

1 The Method
2 Sample Applications
- 2.1 Table Expansion
3 See also
4 External links

[edit] 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 $φ$ 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 + δφ i$ .

The total runtime of the n operations equals $\Sigma_{i=1}^n a_i+\phi_0-\phi_m$ . If $φ$ satisfies $\phi_0-\phi_m\le 0$ then the runtime of all n operations is less or equal the sum of all amortized times.

[edit] Sample Applications

[edit] Table Expansion

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.