2
$\begingroup$

From Introduction to Algorithms by Cormen et al:

In an amortized analysis, the time required to perform a sequence of data structure operations is averaged over all the operations performed.

Amortized analysis can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a single operation within the sequence might be expensive.

Amortized analysis differs from average case analysis in that probability is not involved; an amortized analysis guarantees the average performance of each operation in the worst case.

  1. I thought amortized analysis is for an algorithm. But the above definition says it is for a sequence of (data structure) operations. So I wonder if the sequence of operations as a whole is an algorithm, or each operation is an algorithm?
  2. Can you formulate the definition of amortized analysis in terms of mathematics in order to

    • distinguish it from average case analysis,

    • emphasize that there is no probability of the input involved, and

    • show that it is average performance of each operation in the worse case? (where does it say about worse case in amortized analysis?)

Thanks!

2 Answers 2