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
_{0}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

^{n}_{i=1}^{^}c_{i }^{ }=^{ n}_{i=1}(c_{i }^{ }+ Ψ(D_{i}) - Ψ (D_{i-1}) )

=^{ n}_{i=1}c_{i }^{ }+^{n}_{i=1}Ψ(D_{i}) -^{n}_{i=1}Ψ (D_{i-1})

=^{ n}_{i=1 }c_{i }+ Ψ(D_{1}) + Ψ(D_{2}) + . . . + Ψ (D_{n-1}) + Ψ(D_{n}) - {Ψ(D_{0}) + Ψ(D_{1}) + . . . + Ψ (D_{n-1})

=^{ n}_{i=1}c_{i }^{ }+ Ψ(D_{n}) - Ψ(D_{0}) ----------- (2)

If we define a potential function Ψ so that Ψ(D_{n})
≥ Ψ(D_{0}), then the total amortized cost ^{
n}_{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}) = 0. Since 2^{ëlgi+1û }≤ 2i wherei>0 ,

Therefore, Ψ(D_{i}) ≥ 0 = Ψ(D_{0})

If

i= 2k wherek≥ 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 wherek≥ 0 and 1 ≤ j ≤ 2^{k}then 2^{ëlgi+1û}= 2^{[lgi] }

^{ ^}c_{i }^{ }=^{ }c_{i }+ Ψ(D) - Ψ(D_{i}_{i-1}) = 3

Because ^{n}_{i=1}^{^}c_{i}
_{ }^{ }= ^{n}_{i=1} c_{i }^{ }+
Ψ(D_{n}) - Ψ(D_{0})

and Ψ(D* _{i}*) ≥ Ψ(D

**Application 1- Stack
Operations**

Define the potential function Ψ on a stack to be the number of objects
in the stack. For empty stack D_{0 }, we have Ψ(D_{0})
= 0. Since the number of objects in the stack can not be negative, the stack
D* _{i}* after the i

Ψ(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

) - Ψ(D_{i}_{i-1}) = (s + 1) - s = 1In 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) - Ψ(D_{i}_{i-1}) = 1 + 1 = 2

MULTIPOP

If the i

^{th}operation on the stack is MULTIPOP(S, k) andk` = min(k,s) objects are popped off the stack.The actual cost of the operation is

k`, and the potential difference isΨ(D

) - Ψ(D_{i}_{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) - Ψ(D_{i}_{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*(*n*lg*n*)
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) - Ψ(D_{i}_{i-1})

For the heap operations, this gives us

c_{1}lgn = c_{2}lg(n+c_{3}) + Ψ(D) - Ψ(D_{i}_{i-1}) (Insert) ------------(1)

c_{4}= c_{5}lg(n+ c_{6}) + Ψ(D) - Ψ(D_{i}_{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

_{1}- c_{2})lg(n+ c_{3}) = lg(n!) - lg ((n-1)!) = lgn.This clearly holds if c

_{1}= c_{2}and c_{3}= 0.

From equation (2), we have

c

_{4}- c_{5}lg(n+ c_{6}) = lg(n!) - lg ((n+1)!) = - lg(n+1).This clearly holds if c

_{4}= 0 and c_{4}= c_{6}= 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

Why? Because in addition to resetting t

Therefore, the number of 1's in the counter after the

Ψ(D

) - Ψ(D_{i}_{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+ 1) + (1-_{i }t)_{i}

= 2

If counter starts at zero, then Ψ(D_{0}) = 0. Since
Ψ(D* _{i}*)
≥ 0 for all

If counter does not start at zero, then the initial number are 1's (= b_{0}).

After '*n*' INCREMENT operations the number of 1's = b_{n},
where 0 ≤ b_{0}, b_{n} ≤ *k*.

Since

^{ n}_{i=1}^{^}c_{i}_{ }= (c_{i}_{ }+ Ψ(D_{i}) + Ψ(D_{i-1}))

=>^{ n}_{i=1}^{^}c_{i}_{ }=^{ n}_{i=1 }c_{i}_{ }+^{ n}_{i=1 }Ψ(D) +_{i}^{ n}_{i=1 }Ψ(D_{i-1})

=>^{ n}_{i=1}^{^}c_{i}_{ }=^{ n}S_{i=1 }c_{i}_{ }+^{ }_{ }Ψ(D_{n}) -_{ }Ψ(D_{0})

=>^{ n}_{i=1}c_{i}_{ }=^{ n}_{i=1 }^{^}c_{i}_{ }+^{ }Ψ(D_{0}) -_{ }Ψ(D_{n})

We have ^{^}c_{i}_{ }≤ 2 for all
1≤* i* ≤ *n*. Since
Ψ(D* _{i}*) = b

Since

^{n}_{i=1}c_{i}_{ }=^{ n}_{i=1 }^{^}c_{i}_{ }+^{ }Ψ(D_{n}) +_{ }Ψ(D_{0})

≤^{n}_{i=1 }2 - b_{n }+ b_{0 }why because c_{i}_{ }≤ 2

= 2^{n}_{i=1 }- b_{n }+ b_{0 }= 2n - bn + b

Note that since
b_{0 }≤ *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

Since the actual cost of an ENQUEUE operation is 1, the amortized cost of an ENQUEUE operation is 2. If the

**Case i:**When the second stack is not empty.- In this case we have Ψ(D
) - Ψ(D_{i}_{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