## Potential Method

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:

• D0 is the initial data structure (e.g., stack)
• Di is the data structure after the ith operation.
• ci is the actual cost of the ith operation.
• The potential function Ψ maps each Di to its potential value Ψ(Di)

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

^ci   =  ci + Ψ(Di) - Ψ (Di-1)  --------- (1)

The amortized cost of each operation is therefore

^ci   =  [Actual operation cost] + [change in potential].

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

ni=1 ^ci   =  ni=1(ci   + Ψ(Di) - Ψ (Di-1) )
=  ni=1 ci   ni=1 Ψ(Di) - ni=1Ψ (Di-1)
=  ni=1 ci   + Ψ(D1) + Ψ(D2) +  . . . + Ψ (Dn-1) + Ψ(Dn) - {Ψ(D0) + Ψ(D1) + . . . + Ψ (Dn-1)
=  ni=1 ci   + Ψ(Dn) - Ψ(D0)   ----------- (2)

If  we define a potential function Ψ so that Ψ(Dn)   ≥ Ψ(D0), then the total amortized cost  ni=1 ^ci  is an upper bound on the total actual cost.

As an example consider a sequence of n operations performed on a data structure. The ith 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  Ψ(Di) = 2i - 2ëlgi+1û + 1, then
Ψ(D0) = 0. Since 2ëlgi+1û  ≤  2i where i >0 ,
Therefore,  Ψ(Di)  ≥ 0 = Ψ(D0)

If i = 2k where k ≥ 0 then

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

^ci   =  ci  + Ψ(Di) - Ψ(Di-1)
= i + (2i -2i+1) -{2(i-1)-i+1}
= 2

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

^ci   =  ci  + Ψ(Di) - Ψ(Di-1) = 3

Because  ni=1^ci    ni=1 ci   + Ψ(Dn) - Ψ(D0)

and Ψ(Di)  ≥ Ψ(D0), 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 D0 , we have Ψ(D0) = 0. Since the number of objects in the stack can not be negative, the stack Di after the ith operation has nonnegative potential, and thus

Ψ(Di)  ≥ 0 = Ψ(D0).

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 ith operation on a stack containing s object is a PUSH operation, then the potential difference is

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

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

^ci   =  ci  + Ψ(Di) - Ψ(Di-1) = 1 + 1 = 2

MULTIPOP

If the ith 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

Ψ(Di) - Ψ(Di-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  =  ci  + Ψ(Di) - Ψ(Di-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 ^ci of operation i is defined as

^ci   =  c + Ψ(Di) - Ψ(Di-1)

For the heap operations, this gives us

c1lgn = c2lg(n+c3) + Ψ(Di) - Ψ(Di-1)        (Insert) ------------(1)

c4 = c5lg(n + c6) + Ψ(Di) - Ψ(Di-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

(c1 - c2)lg(n + c3) = lg(n!) - lg ((n-1)!) = lgn.

This clearly holds if c1 = c2 and c3 = 0.

From equation (2), we have

c4 - c5 lg(n + c6) = lg(n!) - lg ((n+1)!) =  - lg(n+1).

This clearly holds if c4 = 0 and c4 = c6 = 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 ith INCREMENT operation to be bi, the number of 1's in the counter after ith operation.

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

Ψ(Di) - Ψ(Di-1)  ≤  (bi-1 - ti + 1) - bi-1 = 1- ti

Putting this value in equation (1), we get

^ci    =     ci + Ψ(Di) - Ψ (Di-1)
=     (ti + 1) + (1- ti)
=     2

If counter starts at zero, then Ψ(D0) = 0. Since Ψ(Di) ≥ 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 (= b0).

After 'n' INCREMENT operations the number of 1's = bn, where 0 ≤  b0, bn ≤  k.

Since   ni=1^ci  = (ci  + Ψ(Di) + Ψ(Di-1))
=>        ni=1^ci  =  ni=1 ci  +  ni=1 Ψ(Di) +  ni=1 Ψ(Di-1)
=>
ni=1^ci  =  nSi=1 ci  +   Ψ(Dn) -  Ψ(D0)
=>         ni=1ci  =  ni=1 ^ci  +  Ψ(D0) -  Ψ(Dn)

We have ^ci  ≤ 2 for all 1≤ in. Since Ψ(Di) = b0 and Ψ(Dn) = b, the total cost of n INCREMENT operation is

Since ni=1ci  =  ni=1 ^ci  +  Ψ(Dn) +  Ψ(D0)
≤ ni=1 2  - bn +  b0  why because ci  ≤ 2
= 2 ni=1   - bn +  b0
= 2n - bn + b

Note that since b0 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 Di denotes the state of the stacks after ith operation. Define Ψ(Di) to be the number of elements in the first stack. Clearly, Ψ(D0) = 0 and Ψ(Di)  ≥ Ψ(D0) for all i. If the ith operation is an ENQUEUE operation, then Ψ(Di) - Ψ(Di-1) = 1
Since the actual cost of an ENQUEUE operation is 1, the amortized cost of an ENQUEUE operation is 2. If the
ith 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 Ψ(Di) - Ψ(Di-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 Ψ(Di) - Ψ(Di-1) =   - Ψ(Di-1) and the actual cost of the DEQUEUE operation is Ψ(Di-1) + 1
.

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