amortized-algorithms

Amortized Analysis

Overview

Amortized analysis is not average-case analysis and does not use probability. It proves that every worst-case operation sequence has small average cost per operation, even when individual operations in that sequence can be expensive.

Core principle: bound the total actual cost of every prefix of the operation sequence by either an aggregate counting argument, nonnegative stored credit, or a nonnegative potential function.

Shared CLRS Conventions

Follow the parent clrs skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style. Keep costs, thresholds, sums, inequalities, and asymptotic bounds in display LaTeX blocks rather than inline prose or table cells.

When an answer needs a threshold such as one half or one quarter, introduce it in prose and then display the exact expression separately.

Operation names may appear in code spans, but mathematical content may not. If a pressure-test answer puts an asymptotic bound, threshold, ratio, variable expression, or inequality in an inline code span or prose sentence, treat the formatting part of the test as failed even when the amortized reasoning is substantively correct.

When to Use

Use this skill for:

• Data-structure operations where an expensive operation consumes work created by earlier cheap operations.
• Stack operations with PUSH, POP, MULTIPOP, or batched deletion from a structure whose items must have been inserted first.
• Binary counters, bit flips, resettable counters, Gray-code-style flip accounting, or carry-chain arguments.
• Dynamic arrays, dynamic tables, resizing policies, load factors, expansion, contraction, and resize thrashing.
• Proofs that ask for aggregate analysis, the accounting method, the potential method, amortized cost, stored credit, or potential functions.
• Production reviews where a textbook amortized guarantee must be tied to handles, resize thresholds, memory movement, latency spikes, or adversarial operation sequences.