What is Amortized Analysis? When is it used? (Hint: Dynamic Arrays)

Amortized analysis is a technique for analyzing the average time complexity of a sequence of operations over the worst case, rather than analyzing a single operation in isolation. It guarantees that even though some individual operations may be expensive, the average cost per operation across a sequence remains bounded, because expensive operations happen infrequently enough to be 'paid off' by the cheaper ones.

A classic example is a dynamic array (like Java's ArrayList or C++'s vector). Most append operations are O(1), but occasionally the array must be resized (typically doubled), which is an O(n) operation. Because doubling happens exponentially less often as the array grows, the amortized cost per append operation over n insertions works out to O(1), even though a single insertion can occasionally be O(n).