Amortized analysis

Amortized analysis is a way to average out the cost of operations over a sequence of operations, rather than looking at the worst-case cost of a single operation.

• It’s useful when some operations are occasionally expensive, but most are cheap.
• It guarantees an average cost per operation, even if some individual operations are costly.

Think of it as “smoothing out” spikes in cost.

2. Why it’s useful

Some data structures have operations that are usually fast but occasionally slow:

• Dynamic arrays: Adding an element is usually (O(1)), but sometimes resizing happens, which costs (O(n)).
• Incrementing a binary counter: Flipping bits can sometimes take multiple steps, but over many increments, the average cost is small.

Amortized analysis lets us say:

“Even though one operation can be expensive, the average cost per operation is low.”

3. Common methods of amortized analysis

There are three main techniques:

(a) Aggregate Method

• Total cost of (n) operations is calculated.
• Then divide by (n) to get the average cost per operation.

Example: Dynamic array

• Suppose we double the array size when full.
• Inserting (n) elements:
• Most insertions = (O(1))
• Resize costs = (1 + 2 + 4 + … + n/2 = O(n))
• Total cost for (n) inserts = (O(n))
• Average cost per insertion = (O(n)/n = O(1))

(b) Accounting Method

• Assign a “credit” to cheap operations to pay for expensive ones later.
• Each operation may pay a little extra to build up credit.

© Potential Method

• Assign a potential function (\Phi) that represents “stored work” in the data structure.
• Amortized cost = actual cost + change in potential.
• Useful when operation costs vary a lot and depend on the current state.

4. Key point

Amortized analysis does not mean the worst-case cost of an operation is low, just that the average cost per operation over many operations is low.