Potential Method

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 D₀, n operations, resulting in D₀, D₁,…, D_n with costs c₁, c₂,…, c_n.

•         A potential function F: {D_i} ^à R (real numbers)

•         F(D_i) is called the potential of D_i.

•         Amortized cost c_i' of the ith operation is:

c_i' = c_i + F(D_i) - F(D_i-1). (actual cost + potential change)

å_i=1ⁿ c_i' = å_i=1ⁿ (c_i + F(D_i) - F(D_i-1))

= å_i=1ⁿc_i + F(D_n) - F(D₀)

•         If F(D_n) ³ F(D₀), then total amortized cost is an upper bound of total actual cost.

•         But we do not know how many operations, so F(D_i) ³ F(D₀) is required for any i.

•         It is convenient to define F(D₀)=0,and so F(D_i) ³0, for all i.

•         If the potential change is positive (i.e., F(D_i) - F(D_i-1)>0), then c_i' 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(D₀)=0, and F(D_i) ³0

•         Amortized cost of stack operations:

–   PUSH:

•         Potential change: F(D_i)- F(D_i-1) =(s+1)-s =1.

•         Amortized cost: c_i' = c_i + F(D_i) - F(D_i-1)=1+1=2.

–   POP:

•         Potential change: F(D_i)- F(D_i-1) =(s-1) –s= -1.

•         Amortized cost: c_i' = c_i + F(D_i) - F(D_i-1)=1+(-1)=0.

–   MULTIPOP(S,k): k'=min(s,k)

•         Potential change: F(D_i)- F(D_i-1) = –k'.

•         Amortized cost: c_i' = c_i + F(D_i) - F(D_i-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(D_i) =b_i, the number of 1‟s. clearly, F(D_i)³0.

•         Let us compute amortized cost of an operation

–   Suppose the ith operation resets t_i bits.

–   Actual cost c_i of the operation is at most t_i +1.

–   If b_i=0, then the ith operation resets all k bits, so b_i-1=t_i=k.

–   If b_i>0, then b_i=b_i-1-t_i+1

–   In either case, b_i£b_i-1-t_i+1.

–   So potential change is F(D_i) - F(D_i-1) £b_i-1-t_i+1-b_i-1=1-t_i.

–   So amortized cost is: c_i' = c_i + F(D_i) - F(D_i-1) £ t_i +1+1-t_i=2.

•         The total amortized cost of n operations is O(n).

•         Thus worst case cost is O(n).