Home | | Programming and Data Structure II | Potential Method

# Potential Method

Same as accounting method: something prepaid is used later.

THE POTENTIAL METHOD:

â€˘         Same as accounting method: something prepaid is used later.

â€˘         Different from accounting method

â€“   The prepaid work not as credit, but as â€śpotential energyâ€ť, or â€śpotentialâ€ť.

The potential is associated with the data structure as a whole rather than with specific objects within the data structure.

â€˘         Initial data structure D0, n operations, resulting in D0, D1,â€¦, Dn with costs c1, c2,â€¦, cn.

â€˘         A potential function F: {Di} Ă  R (real numbers)

â€˘         F(Di) is called the potential of Di.

â€˘         Amortized cost ci' of the ith operation is:

ci' = ci + F(Di) - F(Di-1). (actual cost + potential change)

ĂĄi=1n ci' = ĂĄi=1n (ci + F(Di) - F(Di-1))

= ĂĄi=1nci + F(Dn) - F(D0)

â€˘         If F(Dn) Âł F(D0), then total amortized cost is an upper bound of total actual cost.

â€˘         But we do not know how many operations, so F(Di) Âł F(D0) is required for any i.

â€˘         It is convenient to define F(D0)=0,and so F(Di) Âł0, for all i.

â€˘         If the potential change is positive (i.e., F(Di) - F(Di-1)>0), then ci' is an overcharge (so store the increase as potential), otherwise, undercharge (discharge the potential to pay the actual cost).

Potential method: stack operation

â€˘         Potential for a stack is the number of objects in the stack.

â€˘         So F(D0)=0, and F(Di) Âł0

â€˘         Amortized cost of stack operations:

â€“   PUSH:

â€˘         Potential change: F(Di)- F(Di-1) =(s+1)-s =1.

â€˘         Amortized cost: ci' = ci + F(Di) - F(Di-1)=1+1=2.

â€“   POP:

â€˘         Potential change: F(Di)- F(Di-1) =(s-1) â€“s= -1.

â€˘         Amortized cost: ci' = ci + F(Di) - F(Di-1)=1+(-1)=0.

â€“   MULTIPOP(S,k): k'=min(s,k)

â€˘         Potential change: F(Di)- F(Di-1) = â€“k'.

â€˘         Amortized cost: ci' = ci + F(Di) - F(Di-1)=k'+(-k')=0.

â€˘         So amortized cost of each operation is O(1), and total amortized cost of n operations is O(n).

â€˘         Since total amortized cost is an upper bound of actual cost, the worse case cost of n operations is O(n).

Potential method: binary counter

â€˘         Define the potential of the counter after the ith INCREMENT is F(Di) =bi, the number of 1â€źs. clearly, F(Di)Âł0.

â€˘         Let us compute amortized cost of an operation

â€“   Suppose the ith operation resets ti bits.

â€“   Actual cost ci of the operation is at most ti +1.

â€“   If bi=0, then the ith operation resets all k bits, so bi-1=ti=k.

â€“   If bi>0, then bi=bi-1-ti+1

â€“   In either case, biÂŁbi-1-ti+1.

â€“   So potential change is F(Di) - F(Di-1) ÂŁbi-1-ti+1-bi-1=1-ti.

â€“   So amortized cost is: ci' = ci + F(Di) - F(Di-1) ÂŁ ti +1+1-ti=2.

â€˘         The total amortized cost of n operations is O(n).

â€˘         Thus worst case cost is O(n).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Potential Method |