This method stores pre-payments as potential or potential energy that can be released to pay for future operations. The stored potential is associated with the entire data structure rather than specific objects within the data structure.

Notation:

• D₀ is the initial data structure (e.g., stack)
• D_i is the data structure after the i^th operation.
• c_i is the actual cost of the i^th operation.
• The potential function Ψ maps each D_i to its potential value Ψ(D_i)

The amortized cost  ^{^}c_i  of the ith operation w.r.t potential function Ψ is defined by

^{^}c_i   =  c_i + Ψ(D_i) - Ψ (D_i-1)  --------- (1)

The amortized cost of each operation is therefore

^{^}c_i   =  [Actual operation cost] + [change in potential].

By the eq.I, the total amortized cost of the n operation is

ⁿ_i=1 ^{^}c_i   =  ⁿ_i=1(c_i   + Ψ(D_i) - Ψ (D_i-1) )
                =  ⁿ_i=1 c_i   +  ⁿ_i=1 Ψ(D_i) - ⁿ_i=1Ψ (D_i-1)
                =  ⁿ_i=1 c_i   + Ψ(D₁) + Ψ(D₂) +  . . . + Ψ (D_n-1) + Ψ(D_n) - {Ψ(D₀) + Ψ(D₁) + . . . + Ψ (D_n-1)
                =  ⁿ_i=1 c_i   + Ψ(D_n) - Ψ(D₀)   ----------- (2)

If  we define a potential function Ψ so that Ψ(D_n)   ≥ Ψ(D₀), then the total amortized cost  ⁿ_i=1 ^{^}c_i  is an upper bound on the total actual cost.

As an example consider a sequence of n operations performed on a data structure. The i^th operation costs i if i is an exact power of 2 and 1 otherwise. The potential method of amortized determines the amortized cost per operation as follows:

         Let  Ψ(D_i) = 2i - 2^ëlgi+1û + 1, then
                Ψ(D₀) = 0. Since 2^ëlgi+1û  ≤  2i where i >0 ,
Therefore,  Ψ(D_i)  ≥ 0 = Ψ(D₀)

If i = 2k where k ≥ 0 then

2^ëlgi+1û  = 2^k+1  = 2i
   2^ëlgiû  = 2^k  = i

^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1)
            = i + (2i -2i+1) -{2(i-1)-i+1}
            = 2

If i = 2^k  + j where k  ≥ 0 and 1 ≤  j  ≤  2^k
then 2^ëlgi+1û = 2^[lgi]

   ^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1) = 3
 

Because  ⁿ_i=1^{^}c_i    =  ⁿ_i=1 c_i   + Ψ(D_n) - Ψ(D₀)

and Ψ(D_i)  ≥ Ψ(D₀), so, the total amortized cost of n operation is an upper bound on the total actual cost. Therefore, the total amortized cost of a sequence of n operation is O(n) and the amortized cost per operation is O(n) / n = O(1).

Application 1- Stack Operations

Define the potential function Ψ on a stack to be the number of objects in the stack. For empty stack D₀ , we have Ψ(D₀) = 0. Since the number of objects in the stack can not be negative, the stack D_i after the i^th operation has nonnegative potential, and thus

Ψ(D_i)  ≥ 0 = Ψ(D₀).

Therefore, the total amortized cost of n operations w.r.t. function Ψ represents an upper bound on the actual cost.

Amortized costs of stack operations are:
 

PUSH
 

If the i^th operation on a stack containing s object is a PUSH operation, then the potential difference is

Ψ(D_i) - Ψ(D_i-1) = (s + 1) - s = 1

In simple words, if  i^th is PUSH then (i-1)^th must be one less. By equation I, the amortized cost of this PUSH operation is

     ^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1) = 1 + 1 = 2

 

MULTIPOP
 

If the i^th operation on the stack is MULTIPOP(S, k) and k` = min(k,s) objects are popped off the stack.

The actual cost of the operation is k`, and the potential difference is

Ψ(D_i) - Ψ(D_i-1) =  -k`

why this is negative? Because we are taking off item from the stack. Thus, the amortized cost of the MULTIPOP operation is

    ^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1) = k`-k` = 0

 

POP

Similarly, the amortized cost of a POP operation is 0.

Analysis

Since amortized cost of each of the three operations is O(1), therefore, the total amortized cost of n operations is O(n). The total amortized cost of n operations is an upper bound on the total actual cost.

Lemma     If data structure is Binary heap: Show that a potential function is O(nlgn) such that the amortized cost of EXTRACT-MIN is constant.

Proof

We know that the amortized cost ^{^}c_i of operation i is defined as

^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1)

For the heap operations, this gives us

c₁lgn = c₂lg(n+c₃) + Ψ(D_i) - Ψ(D_i-1)        (Insert) ------------(1)

c₄ = c₅lg(n + c₆) + Ψ(D_i) - Ψ(D_i-1)          (EXTRACT-MIN) -----(2)

Consider the potential function Ψ(D) = lg(n!), where n is the number of items in D.

From equation (1), we have

    (c₁ - c₂)lg(n + c₃) = lg(n!) - lg ((n-1)!) = lgn.

This clearly holds if c₁ = c₂ and c₃ = 0.

 

From equation (2), we have

    c₄ - c₅ lg(n + c₆) = lg(n!) - lg ((n+1)!) =  - lg(n+1).

This clearly holds if c₄ = 0 and c₄ = c₆ = 1.

Remember that stirlings function tells that lg(n!) = θ(nlgn), so

    Ψ(D) = θ(n lg n)

And this completes the proof.

Application 2: Binary Counter

Define the potential of the counter after i^th INCREMENT operation to be b_i, the number of 1's in the counter after i^th operation.

Let i^th INCREMENT operation resets t_i bits. This implies that actual cost = atmost (t_i + 1).
Why? Because in addition to resetting t_i it also sets at most one bit to 1.
Therefore, the number of 1's in the counter after the i^th operation is therefore b_i ≤  b_i-1 - t_i + 1, and the potential difference is

Ψ(D_i) - Ψ(D_i-1)  ≤  (b_i-1 - t_i + 1) - b_i-1 = 1- t_i

Putting this value in equation (1), we get

    ^{^}c_i    =     c_i + Ψ(D_i) - Ψ (D_i-1)
           =     (t_i + 1) + (1- t_i)
          =     2

If counter starts at zero, then Ψ(D₀) = 0. Since Ψ(D_i) ≥ 0 for all i, the total amortized cost of a sequence of n INCREMENT operation is an upper bound on the total actual cost, and so the worst-case cost of n INCREMENT operations is O(n).

If counter does not start at zero, then the initial number are 1's (= b₀).

After 'n' INCREMENT operations the number of 1's = b_n, where 0 ≤  b₀, b_n ≤  k.

Since   ⁿ_i=1^{^}c_i  = (c_i  + Ψ(D_i) + Ψ(D_i-1))
=>        ⁿ_i=1^{^}c_i  =  ⁿ_i=1 c_i  +  ⁿ_i=1 Ψ(D_i) +  ⁿ_i=1 Ψ(D_i-1)
=>        ⁿ_i=1^{^}c_i  =  ⁿS_i=1 c_i  +   Ψ(D_n) -  Ψ(D₀)
=>         ⁿ_i=1c_i  =  ⁿ_i=1 ^{^}c_i  +  Ψ(D₀) -  Ψ(D_n)

We have ^{^}c_i  ≤ 2 for all 1≤ i ≤ n. Since Ψ(D_i) = b₀ and Ψ(D_n) = b, the total cost of n INCREMENT operation is

Since ⁿ_i=1c_i  =  ⁿ_i=1 ^{^}c_i  +  Ψ(D_n) +  Ψ(D₀)
                  ≤ ⁿ_i=1 2  - b_n +  b₀  why because c_i  ≤ 2
                  = 2 ⁿ_i=1   - b_n +  b₀
                  = 2n - bn + b

Note that since b₀ ≤ k, if we execute at least n = Ω(k) INCREMENT Operations, the total actual cost is O(n), no matter what initial value of counter is.

Implementation of a queue with two stacks, such that the amortized cost of each ENQUEUE and each DEQUEUE Operation is O(1). ENQUEUE pushes an object onto the first stack. DEQUEUE pops off an object from second stack if it is not empty. If second stack is empty, DEQUEUE transfers all objects from the first stack to the second stack to the second stack and then pops off the first object. The goal is to show that this implementation has an O(1) amortized cost for each ENQUEUE and DEQUEUE operation. Suppose D_i denotes the state of the stacks after i^th operation. Define Ψ(D_i) to be the number of elements in the first stack. Clearly, Ψ(D₀) = 0 and Ψ(D_i)  ≥ Ψ(D₀) for all i. If the i^th operation is an ENQUEUE operation, then Ψ(D_i) - Ψ(D_i-1) = 1
Since the actual cost of an ENQUEUE operation is 1, the amortized cost of an ENQUEUE operation is 2. If the i^th operation is a DEQUEUE, then there are two case to consider.

Case i: When the second stack is not empty.

 

In this case we have Ψ(D_i) - Ψ(D_i-1) = 0 and the actual cost of the DEQUEUE operation is 1.

 

 

Case ii: When the second stack is empty.

 

In this case, we have Ψ(D_i) - Ψ(D_i-1) =   - Ψ(D_i-1) and the actual cost of the DEQUEUE operation is Ψ(D_i-1) + 1

.

In either case, the amortize cost of the DEQUEUE operation is 1. It follows that each operation has O(1) amortized cost