Potential method

In complexity theory, the potential or potential function method used to measure the amortized time and memory complexity of data structures. The complexity is calculated over a sequence of operations, which distributes the cost of rare but expensive operations to the sequence of operations and thus smooths.

Aim is to assign each operation on the data structure considered an average cost value to estimate the expected life of these any sequence of operations to the top. In contrast to the bank account method, the cost of an operation are not fixed in advance, but derived. For this, a potential function is introduced. This assigns to each internal state of the data structure their potential. Be now the maximum real cost of the operation, the result of amortized cost as:

Applies now that the potential of the initial state for all operations of any sequence of operations is never below:

Then the sum of the real cost is never higher than the amortized cost:

Now exists, for example, a constant that specifies the upper limit of the amortized cost of each operation:

Thus, the total cost of the operation sequence of operations:

Be specified.