[Solved]: How can I make sense of amortized accounting method?

ignougroup
Problem Detail: Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven’t read). In the example of the Stack with Multiple Pops (From CLRS, for reference: http://chuck.ferzle.com/Notes/Notes/AlgorithmAnalysis/Amortized.pdf), we arbitrarily “assigns” a credit of 2 two the Push operation, 0 for pop and 0 for multipop, and each push we arbitrarily “spend” 1 credit and the objected pushed onto the stack “stores” 1 credit. This has to be the most insane thing I have ever seen in my life! Even if I get pass the “why 2 but not 100 credits” stage, how can I rationalize the fact that the object somehow stores a credit? How can we just arbitrarily assign these costs to these operations? Also how could you possibly gain anything insightful from this? It is like imagining that typing on this computer will earn me $100 USD and shutting off the computer will make me spent 20 USD. Can someone please shed a light on how this technique works?

Asked By : Beached Whale

Answered By : hengxin

Amortized analysis is a strategy for analyzing a sequence of operations irrespective of the input to show that the average cost per operation is small, even though a single operation within the sequence might be expensive.

As it is shown in the above quote, amortized analysis is applicable particularly to a sequence of operations in which cheap operations occur frequently and expensive ones occur rarely. Moreover, in an operation sequence, the expensive operation is often related to (OR caused by) the cheap ones before it. For example, in your “Multi-Pop Stack”, the cost of the expensive operation multi-pop(S,k) depends on the number of elements in the stack and thus on the earlier push(S,x) operations. If we focus on a single multi-pop(S,k), we may be disappointed by its expensive cost. Worse still, its cost varies, depending on the current state of the stack when it is issued: if it has popped $t$ elements, then its cost is $t$. By accounting method, we turn to a sequence of operations and attribute (average) the varying cost $t$ of multi-pop(S,k) to the $t$ Push(S,x).

Even if I get pass the “why 2 but not 100 credits” stage, $ldots$

Yes, you can use 100 credits. However, 2 is tighter in terms of worst-case time complexity.

$ldots$ how can I rationalize the fact that the object somehow stores a credit?

“Credit” is only an analogy. We are charging the cost of some (expensive) operations to earlier (cheap) ones. From a different perspective, the earlier (cheap) operations had better save credits for further use of some (expensive) ones.

How can we just arbitrarily assign these costs to these operations?

They are of course not arbitrarily assigned. Instead they are well chosen.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32867