Math Fundamentals18 sections · 814 units
Open in Course

Amortized Analysis

(Average over sequence)

Some operations are expensive occasionally but cheap most of the time. Amortized analysis averages cost over a sequence of operations.

Dynamic array resizing is O(n) when it happens, but it happens rarely. Over n insertions, total cost is O(n), so amortized cost per insertion is O(1).

This is different from average-case analysis. Amortized guarantees hold for any sequence, not just typical inputs.