Cost Over Sequence of Operations

Amortized Analysis

Readers who own a mortgage would probably be aware of amortization. The word amortize means to gradually write off the initial cost of an asset. When undertaking amortized analysis we average the cost of a sequence of operations on a data-structure, even though a single operation may be expensive. This is different than the average case because there's no probability involved and the average time is guaranteed.

There are three ways to conduct amortized analysis

• Aggregate Method
• Accounting Method
• Potential Method

We'll briefly describe each before showing detailed examples.

Aggregate Method

In aggregate method, we find an upper bound on the total cost of a sequence of n operations. Say the upper bound is given by T(n), then the amortized cost is expressed as:
...