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

Amortized analysis evaluates the average cost per operation over a sequence of operations rather than analyzing each operation independently. It is particularly useful for data structures where occasional expensive operations are balanced by many inexpensive operations.

A dynamic array is a classic example. Most append operations are O(1), but when the underlying array becomes full, the implementation may allocate a larger array and copy existing elements, which costs O(n). Because resizing happens infrequently, the amortized cost of append remains O(1).