Amortized Analysis

Why we need it

Big-O worst-case analysis answers: “How bad can one operation be?” That’s important, but it can be misleading for data structures where rare expensive operations are balanced by many cheap ones.

Classic example: dynamic arrays.

• •Most push operations are O(1).
• •Occasionally, the array grows and you copy n elements: O(n).

Worst-case per operation is O(n), but in practice we feel “constant-ish” time. Amortized analysis is the formal proof of that feeling.

The key idea: worst-case over sequences

Amortized analysis is not average-case probability. There is no distribution over inputs.

Instead we fix any sequence of m operations (even an adversarially chosen one), and we show:

∑ (actual cost of op i) ≤ (amortized cost bound) · m + constant

Then the amortized cost per operation is the average upper bound over that sequence.

Formally, if operation i has actual cost cᵢ, we want a bound like:

(1/m) ∑ᵢ cᵢ ≤ O(f(n))

for all sequences of length m, where n is a relevant size parameter (often current number of elements).

Three common proof styles

Amortized analysis usually comes in three equivalent “voices”:

You’ll often start with aggregate to get intuition, then write a clean potential function to make the proof reusable.

What makes a good amortized argument

Two ingredients:

1. 1)A clear model of cost (what counts as 1 unit? comparisons, pointer updates, element moves?)
2. 2)A stored-value story: expensive operations spend work that was “saved up” by previous cheap operations.

That stored value can be literal credits (accounting) or a potential Φ(S) (potential method).

Introducing the potential function Φ(S)

A potential function maps a state S of the data structure to a real number:

Φ(S) ∈ ℝ

Intuition: Φ(S) is “stored credit” or “energy.” If Φ increases, we’re saving credit for later. If Φ decreases, we’re spending credit to subsidize a costly operation.

A standard requirement is:

• •Φ(S) ≥ 0 for all reachable states S
• •Φ(S₀) is usually 0 (or bounded) for the initial empty state S₀

Then we define amortized cost:

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

and show that ĉᵢ ≤ some bound for every operation.

Finally, the magic telescopes:

∑ᵢ ĉᵢ = ∑ᵢ cᵢ + (Φ(S_m) − Φ(S₀))

So if Φ(S_m) ≥ 0 and Φ(S₀) ≥ 0, then:

∑ᵢ cᵢ ≤ ∑ᵢ ĉᵢ + Φ(S₀)

Meaning: bounding amortized costs bounds total actual cost.

This is the formal reason amortized analysis is worst-case over sequences: the inequality holds for every sequence, not “on average.”

Why aggregate analysis comes first

Aggregate analysis is the quickest path to intuition: instead of bounding each operation, you bound the total work across a whole sequence, then divide by m.

This is perfect when expensive events are structured and countable (like “how many resizes can happen?”).

Example pattern: occasional rebuilds

Suppose we have a structure that is cheap most of the time, but sometimes does a rebuild costing proportional to its size.

To use aggregate analysis:

1. 1)Identify the expensive events.
2. 2)Bound how many times they can happen in m operations.
3. 3)Sum their costs.

Dynamic array resizing: total copies are linear in m

Consider a dynamic array that doubles capacity when full.

• •push(x) writes x into the next slot: cost 1.
• •If full, allocate new array of size 2k and copy k elements: cost k (plus the write).

Let’s count element copies over m pushes starting from empty.

Capacities go 1, 2, 4, 8, …

When capacity is k and we grow, we copy k elements.

So total copy cost over all grows up to size m is:

1 + 2 + 4 + … + ⌊m/2⌋ < 2m

because geometric series:

∑_{j=0}^{t} 2ʲ = 2^{t+1} − 1

Thus total actual cost over m pushes is:

• •m writes
• •< 2m copies

So total < 3m, hence amortized cost is < 3 = O(1).

What aggregate analysis gives you (and what it doesn’t)

Aggregate analysis shows:

(1/m) ∑ᵢ cᵢ ≤ constant

But it doesn’t produce a per-operation “bank balance” that composes well with other operations. If you later add pop, shrink, or other behavior, aggregate analysis can become messy.

That’s why we often upgrade to accounting or potential methods: they track stored credit in a way that’s easier to extend.

A second aggregate pattern: bounded number of expensive steps

A surprisingly common amortized trick is:

• •Each operation can do many “small steps” (like while-loops).
• •But each small step can be charged to a unique event (like “this element gets popped once”).

Then total steps over m operations is O(m).

This is the philosophical bridge to the next methods: you’re already doing “charging,” just informally.

Aggregate analysis as a proof template

When you can identify a monotone progress measure (size, capacity, number of items that can be moved), aggregate bounds often become a one-liner:

Total cost ≤ O(total progress)

But when progress can go up and down, you’ll want explicit stored credit (accounting) or explicit Φ(S) (potential).

Why we need “stored credit”

Aggregate analysis is great when behavior is monotone. But many data structures have operations that undo each other (push vs pop) or have multiple interacting costs.

Accounting and potential methods let you say:

• •“This cheap operation will overpay a bit.”
• •“That overpayment is saved.”
• •“Later, a costly operation spends what was saved.”

The result is a uniform amortized bound even if the sequence alternates adversarially.

The accounting (banker’s) method

The rules

You assign each operation i an amortized charge ĉᵢ.

• •You must ensure ĉᵢ ≥ cᵢ − (credits spent on op i)
• •You maintain that the “bank balance” (credits stored) never goes negative.

If the bank never goes negative, then the total amortized charge upper-bounds total actual cost:

∑ᵢ cᵢ ≤ ∑ᵢ ĉᵢ

Intuition: if you always have enough saved credit to pay for extra work, you can’t “cheat.”

A classic example: stack with multipop

Operations on a stack:

• •push(x): cost 1
• •pop(): cost 1 (if nonempty)
• •multipop(k): pop up to k items; cost = number popped

Worst-case multipop(k) is O(n). But amortized, it’s O(1).

Accounting proof idea:

• •Charge push an amortized cost of 2.
• •Use 1 to pay for the push.
• •Store 1 credit on the pushed item.

When an item is popped (by pop or by multipop), spend its stored credit to pay the pop.

Each item is popped at most once, so the credits always suffice.

Thus each operation has amortized O(1).

The potential method

Why potential is more systematic

Accounting attaches credits to “places” (items, nodes, edges). That’s intuitive, but can be ad hoc.

The potential method compresses the entire credit state into a single function:

Φ(S): state → ℝ

Then define amortized cost:

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

If you can prove ĉᵢ ≤ K for every operation (for some constant K), then:

∑ᵢ cᵢ

= ∑ᵢ (ĉᵢ − (Φ(Sᵢ) − Φ(Sᵢ₋₁)))

= ∑ᵢ ĉᵢ − (Φ(S_m) − Φ(S₀))

≤ ∑ᵢ ĉᵢ + Φ(S₀)

And if Φ(S₀) = 0 and Φ(S_m) ≥ 0, then:

∑ᵢ cᵢ ≤ ∑ᵢ ĉᵢ

So bounding amortized costs bounds actual total cost.

How to choose Φ(S)

A good Φ(S) should:

1. 1)Be easy to compute conceptually (even if not computed at runtime).
2. 2)Increase when you do “preparatory work” that will help later.
3. 3)Decrease when an operation is expensive.

Common patterns:

Relating accounting and potential

If accounting stores credits on items, potential is often:

Φ(S) = total stored credits in the structure

So potential can be viewed as “the banker’s balance,” but expressed as a function of state rather than as an explicit ledger.

A small but crucial constraint

Potential functions are typically chosen to be nonnegative on all reachable states:

∀S reachable: Φ(S) ≥ 0

This ensures the telescoping argument yields an upper bound on actual cost.

Sometimes Φ(S) can be negative if you can still bound Φ(S_m) − Φ(S₀), but for most learning-level proofs, keep Φ ≥ 0 to avoid subtle pitfalls.

A note on notation

You’ll often see potential written as Φ, and state as S.

We’ll use:

• •Sᵢ = state after i-th operation
• •ΔΦᵢ = Φ(Sᵢ) − Φ(Sᵢ₋₁)

Then:

ĉᵢ = cᵢ + ΔΦᵢ

Think: amortized = actual + change in stored credit.

If ΔΦᵢ is positive, you’re “saving” credit (amortized > actual).

If ΔΦᵢ is negative, you’re “spending” credit (amortized < actual).

Why this matters beyond toy examples

Amortized analysis shows up whenever a data structure occasionally does heavy maintenance:

• •rebuilding, rebalancing, resizing
• •path compression (Union-Find)
• •garbage collection / compaction strategies

The point is not that worst-case spikes disappear—they don’t. The point is that spikes are paid for by many cheap operations.

How amortized proofs guide design

When you design an algorithm, amortized thinking helps you decide:

• •How aggressive should resizing be? (double vs +constant)
• •When should you rebuild a structure? (every k operations, or when imbalance exceeds a threshold)
• •What invariant should you maintain? (choose one that yields a clean potential)

If you pick the right invariant, you can often get:

• •simple implementation
• •strong worst-case-over-sequences guarantees

Connection to Disjoint Sets (Union-Find)

Union-Find with union by rank/size and path compression has famously fast operations: “near constant.”

That result is typically stated as:

• •A sequence of m operations on n elements costs O(m α(n))
• •where α(n) is the inverse Ackermann function (≤ 4 for all practical n)

This is an amortized statement: single operations can be more expensive, but across the whole sequence the average is tiny.

To understand that proof later, you need comfort with:

• •reasoning about sequences (not single worst cases)
• •charging work to structural progress
• •potential-like arguments (or equivalent accounting)

This node is the prerequisite mindset.

Choosing between methods in practice

Here’s a pragmatic guide:

Mental model you should keep

Amortized analysis is a guarantee about any sequence:

• •Not “typical inputs”
• •Not “random operations”
• •Not “expected value”

It’s deterministic: an adversary can pick the worst possible sequence, and the total cost bound still holds.

That’s why it’s so valuable for core data structures used everywhere.

Checklist for writing your own amortized proof

1. 1)State the operations and cost model.
2. 2)Pick a method (aggregate / accounting / potential).
3. 3)Define what credit means (explicitly or via Φ(S)).
4. 4)Prove credits never go negative (or Φ(S) ≥ 0).
5. 5)Derive the total-cost bound by summing over operations.

Once you can do that reliably, you’re ready to read and trust “near constant amortized time” claims in advanced structures like Union-Find.