Amortised Analysis

In algorithms and data structures, its important to estimate the total time or cost of the sequence of operations performed. However, doing so accurately is challenging:

• Summing worst-case times for each operation leads to overly pessimistic estimates.
• Summing best-case times for each operation leads to overly optimistic estimates..

The issue with average-case analysis is that it requires a meaningful probability distribution over operation sequences, which is hard to define, and even if defined, may still produce _unrealistic estimates-.

Average case analysis can work for algorithms, but fails when it comes to data structures

• For algorithms like sorting, average-case analysis assumes a uniform distribution over inputs.
• For data structures, it’s much harder to define a realistic distribution over operation sequences because usage patterns vary widely and depend on the application context.

Introducing Amortised Analysis

Amortized analysis offers a more realistic way to reason about per-operation cost by analysing the total cost over any sequence of operations.

• It focuses on the average performance per operation across a sequence, not in isolation.
• This often yields tighter bounds than worst-case analysis.
• The key idea is to bound the total cost of all operations in the sequence, providing a more accurate per-operation estimate.

There are three techniques of amortised analysis to find a bound on the true cost of a sequence of operations:

1. Aggregate Method – Analyses the total cost directly and divides it by the number of operation
2. Accounting Method – Assign “credits” to operations to pay for future expensive ones.
3. Potential Method – Uses a potential function to track stored energy (cost) across operations.

We illustrate the three amortisation techniques using a simple data structure: a k-bit binary counter.

Aggregate Method

The aggregate method computes the amortised cost per operation by analysing the total cost of a sequence of operations $T(n)$, and then dividing it evenly across all $n$ operations:

$\text{Amortized cost}=\frac{T(n)}{n}$

This method is effective when a clear bound on the total cost can be derived mathematically for any valid sequence of operations.

Accounting Method

The accounting method treats the data structure as coin-operated, where each operation pays for its cost using a fixed number of coins.

• One coin corresponds to a fixed amount of computation (an $O(1)$ effort).
• Each operation is assigned a fixed number of coins, this is the amortised cost.

If the amortised cost exceeds the actual cost, the extra coins are stored as credit, which can then be used to pay for future expensive operations.

The goal is thus to allocate an amount of coins to some sequence of operation, such that:

• The data structure start with zero credit
• It never goes into debt (i.e. it always has enough credit to cover real costs),

This amount defines the amortised cost of that operation.

If no debt occurs across all possible operation sequences, then the total actual cost is bounded by the sum of amortised costs, giving a tight upper bound on performance.

Potential Method

Define:

• $D_i$ as the state of some data structure after an $i$-th operation that transforms the data structure from $D_{i-1}$ to $D_i$.
• ${\tau }_i$ as the actual time required to perform the $i$-th operation, and
• $a_i$ as the amortised time required to perform the $i$-th operation

Then over $n$ operations, the state evolves as:

$$D_0\underset{{\tau }_1}{\overset{a_1}{\to }}{D}_1\underset{{\tau }_2}{\overset{a_2}{\to }}{D}_2\underset{{\tau }_3}{\overset{a_3}{\to }}\dots \underset{{\tau }_n}{\overset{a_n}{\to }}{D}_n$$

The potential method aims to ensure the total amortised cost bounds the total actual cost:

${\sum }_{i=1}^n{a}_i\ge {\sum }_{i=1}^n{\tau }_i$

Potential Function

Define a potential function $\Phi$ that maps a state $D_i$ of the data structure to a real number $\Phi (D_i)$, called the states potential.

• Interpret one unit of potential as sufficient to pay for a constant unit of actual work.
• This allows work to be stored or released across operations.

Then the amortised cost $a_i$ of the $i$-th operation can be defined as the actual work plus the change in potential:

$$a_i={\tau }_i+\Phi (D_i)-\Phi (D_{i-1})$$

Summing over all $n$ operations results in:

$$\sum _{i=1}^n{a}_i=\sum _{i=1}^n{\tau }_i+\Phi (D_n)-\Phi (D_0)$$

This means that the total amortised cost equals the total actual cost plus the net change in potential.

Derivation Of Above Formula

We sum both sides over all $i=1$ to $n$:

$$\sum _{i=1}^n{a}_i=\sum _{i=1}^n\left[{\tau }_i+\Phi (D_i)-\Phi (D_{i-1})\right]$$

Distribute the summation:

$$\sum _{i=1}^n{a}_i=\sum _{i=1}^n{\tau }_i+\sum _{i=1}^n\left[\Phi (D_i)-\Phi (D_{i-1})\right]$$

The second sum telescopes:

$$\sum _{i=1}^n\left[\Phi (D_i)-\Phi (D_{i-1})\right]=\Phi (D_n)-\Phi (D_0)$$

So we get:

$$\sum _{i=1}^n{a}_i=\sum _{i=1}^n{\tau }_i+\Phi (D_n)-\Phi (D_0)$$

Choosing The Potential Function $\Phi$

If $\Phi (D_n)\ge \Phi (D_0)$, the total amortised cost overestimates the actual cost. So to ensure the amortised analysis yields a valid upper bound on the actual cost, we must have:

$$\Phi (D_n)-\Phi (D_0)\ge 0$$

This condition guarantees:

$$\sum _{i=1}^n{a}_i\ge \sum _{i=1}^n{\tau }_i$$

A common choice is to define a non-negative potential function:

$$\Phi (D_i)\ge 0\text{for all }i,\text{with }\Phi (D_0)=0$$

However, the change in potential between successive operations can be positive or negative:

• $\Phi (D_i)-\Phi (D_{i-1})>0$ is an overcharge, a surplus potential is stored for future use.
• $\Phi (D_i)-\Phi (D_{i-1})<0$ is an undercharge, previously stored potential is used to cover cost.

Different valid potential functions may yield different amortised costs, but all must upper bound the total actual cost. The goal is to choose a $\Phi$ that gives the tightest bound.