ABSTRACT
In this chapter, we briefly discuss amortized analysis, the goal of which is to average the cost of n successive operations. This should not be confused with the average cost of an operation. We first describe the three classical methods with examples (Section 5.1) and then proceed with exercises in Section 5.2, with solutions in Section 5.3.
