7
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Basically, it is a technique used so that most students can understand and use without assuming any prerequisite. General-summation-solving techniques requires some more knowledge of math. $\endgroup$
    – InformedA
    Commented Nov 9, 2014 at 3:25
  • 2
    $\begingroup$ Do you understand the potential technique? It is essentially the same. I think amortized analysis is a cultural thing – the culture is obsessive about money, so the inventors of the terminology thought it would be a helpful and colorful analogy. $\endgroup$
    – Yuval Filmus
    Commented Nov 9, 2014 at 5:23
  • $\begingroup$ The only thing I don't understand is how blase people are when describing this technique. To me it is like a technique invented while someone's doing LSD, or haven't slept for 3 days while wrapping up his PhD thesis. But to people who describe this technique, it is as if this is how the world should be. The logic is not flowing! $\endgroup$
    – Fraïssé
    Commented Nov 9, 2014 at 6:14
  • 1
    $\begingroup$ @randomA The summation method also requires you know well the operation sequence to analyze. $\endgroup$
    – hengxin
    Commented Nov 9, 2014 at 7:53
  • 2
    $\begingroup$ @IllegalImmigrant Please be nice. It's not nice to insult textbook authors (some of which may even be users here!) just because you have trouble understanding something. I recommend you check out some questions about amortized-analysis we alread have. $\endgroup$
    – Raphael
    Commented Nov 10, 2014 at 11:39

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ +1 Good answer, one note though: the 2 is tighter in term of the constant factor. You will still have that 100 or 2 in case of best case or average case analysis. $\endgroup$
    – InformedA
    Commented Nov 9, 2014 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.