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.”

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.

Question: Help understand this:
storing the overcharge as “prepaid credit”
on specific objects in the data structure

Answer:

Given:

  Cost to insert is 1
  Cost to move each value when table is doubled is 1
  Charge for each insert is 3

Insert #1:
cost = 1 (insert: 1)
charge = 3

bankedAmount= 2

bankBalance = 2

NOTE: The bankedAmount is associated with this transaction, but then just put into the account — that is the prepaid credit due to specific object in the data structure.

Insert #2:

cost = 2 (doubleTableAndMove: 1*1 = 1, insert: 1)

charge = 3
bankedAmount= 1
bankBalance = 3

Insert #3:

cost = 3 (doubleTableAndMove: 2*1 = 2, insert: 1)

charge = 3

bankedAmount= 0

bankBalance = 3

Insert #4:

cost = 1 (insert: 1)

charge = 3

bankedAmount= 2

bankBalance = 5

Insert #5:

cost = 5 (doubleTableAndMove: 4*1 = 4, insert: 1)

charge = 3

bankedAmount= -2

bankBalance = 3

etc…

Potential Method:

Question:
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.”

Answer:
Its analogous to the
bank account concept in the accounting method. The potential function
keeps track of the total extra time charged at any time in a sequence
of operations, but it’s only based on the current state of the
structure, regardless of all the operations that put it into that
state.

There’s further explanation with more detail here.

The easiest way to understand amortized worst case analysis is to look at it as the average of the worst case performance over a long sequence of calls. A specific call can perform significantly worse or significantly better than the value, but the average of all the calls you make is going to deterministically approach that value.

Filed under: softwareengineering - @ 15:29

Thẻ: algorithm-analysis, algorithms

Thiết kế website giá rẻ

Danh mục

difference between accounting and potential methods in Amortized Analysis