What is 'Amortized' O(1) in a dynamic array?

What is 'Amortized' O(1) in a dynamic array?

Approach: Explain the cost of resizing averaged over many insertions.

While a resize takes O(n), it only happens every n operations. The total cost of n insertions is O(n), meaning the average cost per insertion is O(1).

Follow-up: Why do we double the size rather than adding a fixed amount?

Key concepts: doubling, geometric series, average cost.