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