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:

$$Amortized\:Cost = \frac{T(n)}{n}$$

In the next section, we show the amortized cost of insertions in a dynamic array using aggregate analysis.

Accounting Method

In the accounting method, we assign costs to each individual operation. The trick is to charge certain operations more than they cost. That way, the extra credit can pay for operations that are charged less but actually cost more. Exercise caution though, as the credit can't fall below zero at any point in the sequence.

Potential Method

The potential method is similar to the accounting method. However, the credit is stored as a whole for the data-structure rather than for individual operations.

One can find data-structures offered in different languages where the costs of various operations on the data-structure are expressed as amortized costs. For instance, in the Java language the ArrayList is one such data-structure which is resizable and has constant amortized cost for insertion.

The intent of this chapter is to give a flavor and reasonable working knowledge of amortized analysis to the reader. Therefore we limit ourselves to examples of the aggregate and accounting methods.