Chapter 17: Amortized Analysis

In an amortized analysis, we average the time required to perform a sequence of data-structure operations over all the operations performed. We can show that the average cost of an operation is small, even though a single operation within the sequence might be expensive.

Key distinction: Amortized analysis differs from average-case analysis in that probability is not involved — it guarantees the average performance of each operation in the worst case.

Three main techniques:

1. Aggregate analysis
2. Accounting method
3. Potential method

---

Aggregate Analysis

In aggregate analysis, we show that for all n, a sequence of n operations takes worst-case time T(n) in total. The amortized cost per operation is therefore:

Amortized cost = T(n) / n

This cost applies to each operation, even when there are several types of operations in the sequence. All operations receive the same amortized cost.

Stack Operations

We augment a standard stack (with O(1) PUSH and POP) with a MULTIPOP operation:

MULTIPOP(S, k)
1  while not STACK-EMPTY(S) and k > 0
2      POP(S)
3      k = k - 1

• MULTIPOP(S, k) removes the top min(s, k) objects from stack S (where s is the current stack size)
• Cost of MULTIPOP = min(s, k)

Naive analysis:

• Worst-case cost of a single MULTIPOP is O(n) (stack could have n items)
• Sequence of n operations: O(n²) — not tight

Aggregate analysis:

• Each object can be popped at most once for each time it was pushed
• Total POPs (including those within MULTIPOP) ≤ total PUSHes ≤ n
• Total cost of n operations = O(n)
• Amortized cost per operation = O(n)/n = O(1)

Incrementing a Binary Counter

A k-bit binary counter counts upward from 0 using an array A[0..k−1]:

INCREMENT(A)
1  i = 0
2  while i < A.length and A[i] == 1
3      A[i] = 0
4      i = i + 1
5  if i < A.length
6      A[i] = 1

Naive analysis:

• Single INCREMENT takes Θ(k) worst case (all bits are 1)
• Sequence of n operations: O(nk) — not tight

Aggregate analysis:

• Bit A[0] flips every time: n flips
• Bit A[1] flips every other time: ⌊n/2⌋ flips
• Bit A[i] flips ⌊n/2ⁱ⌋ times

Total flips:

Σ (i=0 to k−1) ⌊n/2ⁱ⌋ < n · Σ (i=0 to ∞) 1/2ⁱ = 2n

• Total cost of n INCREMENTs = O(n)
• Amortized cost per operation = O(1)

---

The Accounting Method

In the accounting method, we assign differing charges (amortized costs) to different operations. When an operation's amortized cost exceeds its actual cost, the difference is stored as "prepaid credit" on specific objects in the data structure. Later operations use this credit to pay for costs that exceed their amortized charges.

Key requirement: The total amortized cost must be an upper bound on the total actual cost for all sequences of operations:

Σ ĉᵢ ≥ Σ cᵢ (for all sequences of n operations)

Equivalently, the total credit in the data structure must remain nonnegative at all times.

Stack Operations

Intuition:

• When we PUSH a plate, we pay 1 dollar for the push and leave 1 dollar of credit on the plate
• Every plate on the stack always has $1 of credit
• POP and MULTIPOP use the stored credit to pay their actual costs
• Credit is always nonnegative (≥ 0 plates on the stack)

Total amortized cost of n operations = O(n), so total actual cost is also O(n).

Incrementing a Binary Counter

• Charge an amortized cost of $2 to set a bit to 1
  • $1 pays for the actual setting
  • $1 is placed on the bit as credit for future resetting
• Charge $0 to reset a bit to 0 (paid by the credit on the bit)

Since INCREMENT sets at most one bit to 1 (in line 6), the amortized cost per INCREMENT is at most $2.

The number of 1s in the counter is never negative → credit stays nonnegative → total amortized cost O(n) bounds total actual cost.

---

The Potential Method

The potential method represents prepaid work as "potential energy" associated with the data structure as a whole (not individual objects).

Framework

• Start with initial data structure D₀
• After the ith operation: data structure Dᵢ, actual cost cᵢ
• Potential function Φ maps each Dᵢ to a real number Φ(Dᵢ)

Amortized cost of the ith operation:

ĉᵢ = cᵢ + Φ(Dᵢ) − Φ(Dᵢ₋₁)

Total amortized cost (telescoping sum):

Σ ĉᵢ = Σ cᵢ + Φ(Dₙ) − Φ(D₀)

Requirement: If Φ(Dₙ) ≥ Φ(D₀), then total amortized cost is an upper bound on total actual cost. In practice, define Φ(D₀) = 0 and show Φ(Dᵢ) ≥ 0 for all i.

Intuition:

• Positive potential difference → amortized cost is an overcharge (potential increases)
• Negative potential difference → amortized cost is an undercharge (potential pays for actual cost)

Stack Operations

Potential function: Φ = number of objects in the stack

• Φ(D₀) = 0, and Φ(Dᵢ) ≥ 0 for all i

(where k' = min(k, s))

All amortized costs are O(1) → total for n operations is O(n).

Incrementing a Binary Counter

Potential function: Φ(Dᵢ) = bᵢ (number of 1s in the counter after the ith operation)

If the ith INCREMENT resets tᵢ bits:

• Actual cost: cᵢ ≤ tᵢ + 1
• Potential change: Φ(Dᵢ) − Φ(Dᵢ₋₁) ≤ 1 − tᵢ
• Amortized cost: ĉᵢ ≤ (tᵢ + 1) + (1 − tᵢ) = 2

Since Φ(D₀) = 0 and Φ(Dᵢ) ≥ 0, the worst-case cost of n INCREMENTs is O(n).

Non-zero start: If the counter starts with b₀ ones and ends with bₙ ones:

Σ cᵢ ≤ 2n − bₙ + b₀

As long as k = O(n) (i.e., we execute at least n = Ω(k) operations), the total actual cost is O(n) regardless of the initial counter value.

---

Dynamic Tables

A dynamic table automatically expands or contracts as items are inserted or deleted. Using amortized analysis, the amortized cost of insertion and deletion is O(1), even though individual operations that trigger expansion or contraction are expensive.

Key definitions:

• Load factor α(T) = T.num / T.size (number of items / number of slots)
• Empty table: size = 0, load factor = 1 (by convention)

Table Expansion

When inserting into a full table, allocate a new table with twice the slots and copy all items over.

TABLE-INSERT(T, x)
 1  if T.size == 0
 2      allocate T.table with 1 slot
 3      T.size = 1
 4  if T.num == T.size
 5      allocate new-table with 2 · T.size slots
 6      insert all items in T.table into new-table
 7      free T.table
 8      T.table = new-table
 9      T.size = 2 · T.size
10  insert x into T.table
11  T.num = T.num + 1

• Load factor is always ≥ 1/2 (wasted space ≤ half of total)
• Expansion occurs only when i−1 is an exact power of 2

Aggregate analysis:

Cost of the ith operation:

• cᵢ = i, if i−1 is an exact power of 2 (expansion)
• cᵢ = 1, otherwise

Σ cᵢ ≤ n + Σ (j=0 to ⌊lg n⌋) 2ʲ < n + 2n = 3n

Amortized cost per TABLE-INSERT = at most 3.

Accounting method intuition:

Each item pays for 3 elementary insertions:

1. Inserting itself into the current table
2. Moving itself when the table expands
3. Moving one other item that has already been moved once

Potential method:

Φ(T) = 2 · T.num − T.size

Properties:

• After expansion: T.num = T.size/2, so Φ = 0
• Before expansion: T.num = T.size, so Φ = T.num (enough to pay for copying)
• Always Φ ≥ 0 (since table is always at least half full)

Amortized cost of TABLE-INSERT:

• Without expansion: ĉᵢ = 1 + (2·numᵢ − sizeᵢ) − (2·(numᵢ−1) − sizeᵢ) = 3
• With expansion: ĉᵢ = numᵢ + (2·numᵢ − 2·(numᵢ−1)) − (2·(numᵢ−1) − (numᵢ−1)) = 3

Table Expansion and Contraction

Naive contraction strategy (halve at 1/2 full):

• Leads to thrashing — alternating insertions and deletions near the boundary cause repeated expansions/contractions
• Amortized cost degrades to Θ(n) per operation

Better strategy:

• Expand (double) when load factor reaches 1 (table is full)
• Contract (halve) when load factor drops below 1/4
• Load factor is always bounded below by 1/4

Potential function for expansion + contraction:

Φ(T) = 2 · T.num − T.size, if α(T) ≥ 1/2 Φ(T) = T.size/2 − T.num, if α(T) < 1/2

Properties:

• Φ = 0 when α = 1/2 (ideal state)
• Φ = T.num when α = 1 (ready to pay for expansion)
• Φ = T.num when α = 1/4 (ready to pay for contraction)
• Φ ≥ 0 always

Amortized costs (all bounded by constants):

Since every operation has O(1) amortized cost, any sequence of n TABLE-INSERT and TABLE-DELETE operations on a dynamic table runs in O(n) time.

---

Summary of Techniques