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."
Best Answer
Accounting Method:
The accounting method works to determine a payment of some extra time units charged to each individual operation so that the sum of all payments isn't exceeded by the total actual cost.
You can think about it like a bank account where you charge a little more than actual cost for each and bank extra in a pool so that very high-cost operations can be charged less than their actual cost, paid for by the pool of savings. This spreads out the high-cost operations over the entire sequence.
The charges for each operation need to be big enough to keep the balance in the account positive while being small enough so as to not significantly overcharge the operation above its actual cost.
Potential Method:
There's further explanation with more detail here.