Amortized Analysis

Learning Objectives

By the end of this section, you will be able to:

1. Understand amortized analysis and how it differs from worst-case and average-case analysis
2. Apply the aggregate method to calculate average cost over a sequence of operations
3. Master the accounting method by assigning charges that pay for expensive operations
4. Use the potential method to analyze data structures using a potential function
5. Prove that dynamic array push is O(1) amortized using all three methods
6. Recognize when amortized analysis applies in real-world data structures

Why This Matters: Amortized analysis is essential for understanding the true performance of data structures like dynamic arrays (std::vector, ArrayList), hash tables, and self-balancing trees. Without it, you would incorrectly conclude that dynamic arrays have O(n) push operations—a claim that contradicts everyday programming experience.

The Problem: Why Worst-Case Lies

Consider the humble dynamic array—the ArrayList in Java, std::vector in C++, or list in Python. You've used it countless times:

1arr = []
2for i in range(1000000):
3    arr.append(i)  # What's the cost of this?

If you do a naive worst-case analysis, you might reason:

• When the array is full, append must copy all n elements to a new, larger array
• Therefore, worst-case cost of append is $O(n)$
• So n appends would cost $O(n^2)$!

But this analysis is misleading. In practice, those million appends complete nearly instantly. The worst-case analysis gives a true but useless bound—it tells us each operation might be expensive, but ignores that expensive operations are rare.

What is Amortized Analysis?

Amortized analysis determines the average performance of an operation in a sequence, guaranteeing the average cost over that sequence even in the worst case.

Key Characteristics

The Key Insight

Unlike average-case analysis, amortized analysis does not involve probability. It provides a guaranteed average per operation over any sequence of operations. The idea is:

If we can prove that n operations cost at most $cn$ (for some constant c), then the amortized cost is $O(1)$.

Intuition: Amortized analysis "spreads out" the cost of expensive operations over many cheap ones. It's like a subscription service—you pay a steady monthly fee rather than paying per-use with occasional huge bills.

Running Example: Dynamic Arrays

Throughout this section, we'll analyze a dynamic array with a doubling strategy:

The Data Structure

• Start with an array of capacity 1
• When pushing to a full array, allocate a new array of twice the capacity
• Copy all existing elements to the new array, then insert the new element

Cost Model

• Inserting an element into an available slot costs 1
• Copying an element during resize costs 1
• So resizing n elements and inserting costs n + 1

Cost Sequence Example

Let's trace the cost of pushing elements 1, 2, 3, ..., 8:

After 8 pushes, total cost = 15. Amortized cost = 15/8 = 1.875 per push!

Interactive: Dynamic Array Costs

Watch how push operations affect the total cost and amortized cost. Notice how the amortized cost stays close to 3 even when individual operations spike during resizes.

The Aggregate Method

The aggregate method is the most straightforward approach: calculate the total cost of n operations, then divide by n.

Approach

1. Compute an upper bound on the total cost of n operations
2. Divide by n to get the amortized cost per operation
3. All operations get the same amortized cost

Analysis for Dynamic Array

For n push operations on a dynamic array that doubles:

Step 1: Count the Total Cost

Each push costs 1 for insertion. Additionally, resize operations cost:

• Push 2: copy 1 element
• Push 3: copy 2 elements
• Push 5: copy 4 elements
• Push 9: copy 8 elements
• In general: copy $2^k$ elements at push $2^k + 1$

Total copy cost for n pushes:

Step 2: Sum Total Costs

Step 3: Compute Amortized Cost

The Accounting Method (Banker's Method)

The accounting method assigns different "charges" to different operations. Some operations are overcharged; the extra credit pays for future expensive operations.

The Key Rule

The total amortized cost must always be at least the total actual cost. We can never "go into debt."

where $\hat{c}_i$ is the amortized cost and $c_i$ is the actual cost.

Analysis for Dynamic Array

We assign an amortized cost of 3 to each push operation:

• 1 credit pays for the actual insertion
• 2 credits are stored with the element for future copying

Why This Works

When a resize happens from capacity c to 2c:

• We need to copy c elements (cost = c)
• The last c/2 elements were added since the previous resize
• Each of those c/2 elements has 2 stored credits
• Total stored: $c/2 \times 2 = c$ credits—exactly enough!

Visualization

Think of each element carrying 2 "coins":

• 1 coin to pay for copying itself in the next resize
• 1 coin to "sponsor" an older element that has already spent its coins

Interactive: Accounting Method

Watch the accounting method in action. Each push is charged 3 credits, with 2 stored for future copies. When a resize occurs, stored credits pay for copying.

The Potential Method (Physicist's Method)

The potential method is the most powerful and general technique. It defines a potential function that maps the data structure state to a non-negative real number, representing "stored energy."

The Framework

Define a potential function $\Phi: \text{States} \rightarrow \mathbb{R}$ such that:

• $\Phi(D_0) = 0$ (initial state has zero potential)
• $\Phi(D_i) \geq 0$ for all states (potential is never negative)

The amortized cost of the i-th operation is:

That is: amortized cost = actual cost + change in potential.

Why This Works

Summing over n operations:

Since $\Phi(D_n) \geq 0$ and $\Phi(D_0) = 0$:

The sum of amortized costs is an upper bound on actual costs!

Analysis for Dynamic Array

Define the potential function:

where n = number of elements, c = capacity.

Case 1: No Resize (n < c before push)

• Actual cost: $c_i = 1$
• Potential change: $\Delta\Phi = 2(n+1) - c - (2n - c) = 2$
• Amortized: $\hat{c}_i = 1 + 2 = 3$

Case 2: Resize Needed (n = c before push)

• Actual cost: $c_i = n + 1$ (copy n elements + insert)
• New state: n+1 elements, capacity 2c = 2n
• Potential change: $\Delta\Phi = 2(n+1) - 2n - (2n - n) = 2 - n$
• Amortized: $\hat{c}_i = (n+1) + (2-n) = 3$

Interactive: Potential Method

Explore how the potential function tracks "stored energy" in the data structure. Notice how when expensive resize operations occur, the potential drops significantly, canceling out the high actual cost.

Comparing the Three Methods

When to Use Each

• Aggregate: Start here. If you can sum up total cost easily, this is the simplest approach.
• Accounting: Use when you need to "prepay" for future operations. Good for intuitive explanations.
• Potential: Use for complex analyses, especially when operations interact in complicated ways. The potential function often reveals deep structure.

Implementation in Code

Let's implement a dynamic array from scratch, tracking costs to verify our analysis.

1 → 2 → 4 → 8 → 16 → ...

1class DynamicArray:
2    """Dynamic array with cost tracking for amortized analysis."""
3
4    def __init__(self):
5        self.data = [None]  # Initial capacity of 1
6        self.size = 0
7        self.capacity = 1
8        self.total_cost = 0
9        self.push_count = 0
10
11    def push(self, value):
12        """Push value to array. Returns cost of this operation."""
13        cost = 1  # Cost for insertion
14
15        # Check if resize needed
16        if self.size >= self.capacity:
17            # Double the capacity
18            new_capacity = self.capacity * 2
19            new_data = [None] * new_capacity
20
21            # Copy all elements (each copy costs 1)
22            for i in range(self.size):
23                new_data[i] = self.data[i]
24                cost += 1  # Cost for each copy
25
26            self.data = new_data
27            self.capacity = new_capacity
28
29        # Insert the new element
30        self.data[self.size] = value
31        self.size += 1
32
33        # Track costs
34        self.total_cost += cost
35        self.push_count += 1
36        return cost
37
38    def amortized_cost(self):
39        """Return current amortized cost per operation."""
40        if self.push_count == 0:
41            return 0
42        return self.total_cost / self.push_count
43
44    def potential(self):
45        """Calculate potential function: Φ = 2n - c"""
46        return 2 * self.size - self.capacity
47
48
49# Demonstrate amortized analysis
50arr = DynamicArray()
51
52print("Push | Cost | Total | Amortized | Potential")
53print("-" * 50)
54
55for i in range(1, 17):
56    cost = arr.push(i)
57    amort = arr.amortized_cost()
58    phi = arr.potential()
59    print(f"  {i:2d} |  {cost:2d}  |  {arr.total_cost:3d}  |   {amort:.2f}    |    {phi:2d}")
60
61print()
62print(f"Final amortized cost: {arr.amortized_cost():.3f}")
63print(f"Theoretical bound: 3.0")

C Implementation

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5typedef struct {
6    int* data;
7    int size;
8    int capacity;
9    int total_cost;
10    int push_count;
11} DynamicArray;
12
13DynamicArray* create_array() {
14    DynamicArray* arr = malloc(sizeof(DynamicArray));
15    arr->data = malloc(sizeof(int));
16    arr->size = 0;
17    arr->capacity = 1;
18    arr->total_cost = 0;
19    arr->push_count = 0;
20    return arr;
21}
22
23int push(DynamicArray* arr, int value) {
24    int cost = 1;  // Base cost for insertion
25
26    // Resize if needed
27    if (arr->size >= arr->capacity) {
28        int new_cap = arr->capacity * 2;
29        int* new_data = malloc(new_cap * sizeof(int));
30
31        // Copy all elements (each costs 1)
32        memcpy(new_data, arr->data, arr->size * sizeof(int));
33        cost += arr->size;  // Add copy cost
34
35        free(arr->data);
36        arr->data = new_data;
37        arr->capacity = new_cap;
38    }
39
40    // Insert element
41    arr->data[arr->size] = value;
42    arr->size++;
43
44    arr->total_cost += cost;
45    arr->push_count++;
46    return cost;
47}
48
49double amortized_cost(DynamicArray* arr) {
50    if (arr->push_count == 0) return 0.0;
51    return (double)arr->total_cost / arr->push_count;
52}
53
54void free_array(DynamicArray* arr) {
55    free(arr->data);
56    free(arr);
57}
58
59int main() {
60    DynamicArray* arr = create_array();
61
62    printf("Push | Cost | Total | Amortized\n");
63    printf("-----------------------------------\n");
64
65    for (int i = 1; i <= 16; i++) {
66        int cost = push(arr, i);
67        printf("  %2d |  %2d  |  %3d  |   %.2f\n",
68               i, cost, arr->total_cost, amortized_cost(arr));
69    }
70
71    printf("\nFinal amortized cost: %.3f\n", amortized_cost(arr));
72
73    free_array(arr);
74    return 0;
75}

Real-World Applications

Amortized analysis is crucial for understanding the performance of many common data structures:

1. Hash Tables

Hash tables resize when the load factor exceeds a threshold. Similar to dynamic arrays, this gives $O(1)$ amortized insert/lookup despite occasional $O(n)$ rehashing.

2. Splay Trees

Splay trees have $O(\log n)$ amortized operations, even though individual operations can be $O(n)$. The potential method is essential for analyzing them.

3. Union-Find (Disjoint Set)

With path compression and union by rank, Union-Find achieves $O(\alpha(n))$ amortized time per operation, where $\alpha$ is the inverse Ackermann function (effectively constant).

4. Fibonacci Heaps

Fibonacci heaps have $O(1)$ amortized insert, find-min, and decrease-key operations, enabling efficient implementations of Dijkstra's and Prim's algorithms.

Test Your Understanding

Summary

Amortized analysis reveals the true cost of data structure operations by considering sequences rather than individual worst cases.

Key Concepts

Key Takeaways

1. Worst-case per-operation can be misleading when expensive operations are rare
2. Amortized analysis provides guaranteed average cost without probabilistic assumptions
3. Three methods: Aggregate (easiest), Accounting (intuitive), Potential (most powerful)
4. Dynamic array push is O(1) amortized, which is why vectors/ArrayLists are so efficient
5. The potential method can prove tight bounds for complex data structures

Exercises

Conceptual Questions

1. Tripling Strategy: Suppose a dynamic array triples its capacity instead of doubling. Prove that push is still $O(1)$ amortized. What is the constant factor compared to doubling?
2. Incrementing by 1: If a dynamic array increases capacity by 1 (instead of doubling), what is the amortized cost of push? Prove your answer.
3. Multipop Stack: Consider a stack with push (cost 1) and multipop(k) that removes k items (cost min(k, size)). Using the potential function $\Phi = \text{size of stack}$, prove that both operations are $O(1)$ amortized.
4. Binary Counter: A binary counter starts at 0. The INCREMENT operation flips bits from rightmost until finding a 0, then flips it to 1. Prove INCREMENT is $O(1)$ amortized using the potential $\Phi = \text{number of 1 bits}$.

Coding Exercises

1. Implement and Verify: Implement a dynamic array that tracks costs per operation. Run 1 million pushes and verify that the amortized cost approaches 3.
2. Shrinking Array: Extend the dynamic array to shrink (halve capacity) when size drops below 1/4 capacity. Analyze the amortized cost of pop operations.
3. Visualize Potential: Create a visualization that shows the potential function value after each operation for both push and pop on a dynamic array.

Challenge Problems

1. Two-Stack Queue: A queue can be implemented using two stacks. Analyze the amortized cost of enqueue and dequeue operations.
2. Splay Tree Analysis: Research and explain the Access Lemma used in splay tree amortized analysis. What potential function is used?
3. Hash Table Load Factor: If a hash table resizes when load factor exceeds 0.75 and doubles capacity, prove that insert is $O(1)$ amortized. What changes if we resize at 0.5?

In the next section, we'll explore the Master Theorem—a powerful tool for solving recurrence relations that arise from divide-and-conquer algorithms.