Amortized analysis
Applies to: general
Amortized analysis measures the average cost of an operation across a sequence, rather than the worst single case. A dynamic array's append is O(n) on the rare resize but O(1) amortized, because resizes are infrequent enough to average out.
n appends, occasional doubling -> total O(n) -> O(1) each, amortized