1
$\begingroup$

I'm reading through CLRS again and I was wondering if there's a formal justification or construction of the accounting method, explaining why it works. For some reason it seems to me that CLRS basically expose the method explaining the intuition behind it, but it doesn't seem rigorous to me.

Also is it correct to say that the accounting method is essentially a method to derive the actual cost of a sequence of $n$ operations by assigning a suitable ammortized cost to each operation?

This should differ from aggregate analysis, where we try to derive a worst case cost and then we derive the ammortized cost (kind of the inverse in some sense).

To this stage the accounting method seems to me like a "recipe" to derive a bound, in doesn't seem to convey anything else to be honest.

$\endgroup$
  • $\begingroup$ "if there's a formal justification or construction of the accounting method" -- there some simple inequalities that have to hold. Done. $\endgroup$ – Raphael Mar 7 '18 at 19:53
  • $\begingroup$ "Also is it correct to say that the accounting method is essentially a method to derive the actual cost of a sequence of n operations by assigning a suitable ammortized cost to each operation?" -- No, it's the other way around. We calculate (or estimate) the cost of a sequence of operations, and then assign each individual operation an equal share of the cost, which we call "amortized cost". Note that this is independ of worst- vs average-case; you can perform amortized analysis for any case. $\endgroup$ – Raphael Mar 7 '18 at 19:54
  • $\begingroup$ @Raphael, it doesn't seem to me in that way. You assign an a cost $\hat{c}_i$, which is defined by the book has amortized cost, and then you perform the summation over $n$ operation, and this is an over estimation of the actual of costs over a sequence of $n$ operations. About the "formality" I agree it is an inequality that does have to old... it's just the idea of assigning costs in that way that seems weird. $\endgroup$ – user8469759 Mar 8 '18 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.