Dear All,

My question is about Accounting method-in Amortized Analysis

Im studying the "Introduction to Algorithms book",

I finding some problems understanding the idea behind the "Accounting argument " in the Amortized chapter.

i understood the example of the stack and how it goes...but the thing i didnt understand is "SO WHAT I GRAP A PAPER AND ASSIGN AN AMORTIZED COST FOR THE PUSH TO BE 2 AND POP AND MULTIPOP TO BE ZERO"....


operation ................ actual cost............... amortized cost....
PUSH ...........................1...............................2....
POP..............................1...............................0...
MULTIPOP.....................min(k,s)..................... 0....


after all , when i run the code each of the operation will take time...pop and multipop would still costs us some time !...( there is no way they will cost us 0!!!!!)


i dont get the USE behind we overcharge some operations on a PAPER and then do the analysis ! ..i mean the code and the running time would still be the same...because inside the computer i CANNOT charge an operation ! .... please help me understand the concept...because once i do...the "potentiall method " should become easier to grasp too.

thank you in advance