If inserting into a dynamic array can cost O(n) when it has to resize, how can it be O(1)?
The answer is amortization. And understanding it changes how you think about the cost of dynamic data structures.
What amortized complexity is
Amortized complexity measures the average cost per operation across a long sequence of operations. It does not analyze operations in isolation — it analyzes the total cost spread across all of them.
The idea is that occasionally expensive operations get "paid for" with credit accumulated from many earlier cheap operations.
The classic pattern: many cheap insertions → expensive resize → many cheap insertions → expensive resize → ...
Even though the resize is O(n), it happens so rarely that the average cost per insertion is still O(1).
Aggregate method
The most intuitive one: add up the total cost of n operations and divide by n.
Example: inserting 8 elements into a dynamic array that starts with capacity 1 and doubles when it fills up.
| Insertion | Cost |
|---|---|
| 1 (+ resize 1→2) | 1 + 1 = 2 |
| 2 (+ resize 2→4) | 1 + 2 = 3 |
| 3 | 1 |
| 4 (+ resize 4→8) | 1 + 4 = 5 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
Total cost: 15 units. Average: 15 / 8 = 1.875 ≈ amortized O(1).
Accounting method
You assign "credits" to each operation. Cheap operations bank credits that finance the expensive ones.
Rule: each insertion costs 2 credits.
- 1 credit pays for the current insertion
- 1 credit is saved for the future resize
The validity condition: credits must never go negative. If at any point the balance dips below zero, the strategy does not hold and the amortized cost is not O(1).
With an array that doubles (×2), the credits always stay positive. Why? Because each resize moves exactly as many elements as were inserted since the last resize, and every one of those elements already banked its credit.
Counter-example: if the array grew by +1 instead of ×2, the credits would eventually go negative. That is a formal proof that the strategy is inefficient.
Potential method
The most mathematically rigorous one. It defines a potential function Φ that measures the "accumulated energy" in the structure.
For a dynamic array: Φ = 2 × elements − capacity
The validity condition: Φ can never be negative.
The amortized cost of each operation is defined as:
Amortized cost = Actual cost + ΔΦ
Where ΔΦ is the change in potential after the operation.
For an insertion with no resize: actual cost = 1, Φ increases by 2, amortized cost = 1 + 2 = 3. Constant, though higher than the actual cost — those extra 2 are the credit banked to pay for the resize.
The key is the insertion with a resize: actual cost = n+1 (move n elements + insert), Φ drops from n to 2 — that is, ΔΦ = 2−n — so amortized cost = (n+1) + (2−n) = 3. Constant.
The potential method has the advantage of lending itself to rigorous formal proofs — it is the tool academic papers use.
The three methods compared
| Method | Mechanism | When to use it |
|---|---|---|
| Aggregate | Total sum ÷ n | Simple analysis, big picture |
| Accounting | External credits | Intuitive explanations, presentations |
| Potential | Internal energy function | Rigorous formal proofs |
All three reach the same conclusion: inserting into a dynamic array is amortized O(1).
Why it matters in practice
When you use ArrayList in Java, vector in C++, or a list in Python, you are using structures with amortized complexity. The occasional cost of the resize is "prepaid" by the insertions before it.
This also explains why doubling (×2) is the right growth strategy and growing one at a time is not. With ×2, the amortized cost is O(1). With +1, it is O(n). That is a difference of orders of magnitude disguised as an implementation detail.