Friday, 23 August 2013

difference between accounting and potential methods in Amortized Analysis

difference between accounting and potential methods in Amortized Analysis

I was going through the Introduction to Algorithms by Cormen et al.In the
chapter titled Amortized Analysis,the difference between accounting and
potential methods is given like this
The accounting method overcharges some operations early in the sequence,
storing the overcharge as "prepaid credit" on specific objects in the data
structure. ...
The potential method maintains the credit as the "potential energy" of the
data structure as a whole instead of associating the credit with
individual objects within the data structure.
I tried to understand this using the example of resizable array which
doubles its size when there is no space to insert an element.What I
couldn't understand was the following sentence
storing the overcharge as "prepaid credit" on specific objects in the data
structure
Using Accounting method:
ci = the charge for the i-th operation
c'i = amortized cost of the i-th operation
Si = array size after the i-th operation
bi = balance of credit after the i-th operation
i 1 2 3 4 5 6 7 8 9 10
si 1 2 4 4 8 8 8 8 16 16
ci 1 2 3 1 5 1 1 1 9 1
c'i 3 3 3 3 3 3 3 3 3 3
bi 2 3 3 5 3 5 7 9 3 5
what exactly does "storing on specific objects in the data structure" mean
here?
In potential method ,if I use phi to be 2n-m where n = number of currebt
elements in the array ,and m=array size
n m phi
empty 0 0 0
add first elem 1 1 1
add secondelem 2 2 2
add third elem 3 4 2
add fourth elem 4 4 4
add fifth elem 5 8 2
In this ,what does it mean by "...the "potential energy" of the data
structure as a whole instead of associating the credit with individual
objects within the data structure."

No comments:

Post a Comment