Questions
3 of 19
Explain the concept of Amortized O(1) for Dynamic Array insertion.
Difficulty: 3/10
Amortized Analysis
Appending to a dynamic array is amortized O(1) because most insertions require only one write, while the occasional resize costs O(n). With geometric growth, the total cost of all resizes over many insertions is linear, so the average cost per insertion remains constant.
javascript
- 1
An individual resize can be O(n).
- 2
Resizing happens only occasionally when capacity is exhausted.
- 3
Geometric growth prevents resizing on every insertion.
- 4
Across n insertions, total copying work is O(n).
- 5
Therefore, append is amortized O(1), although its worst-case individual operation can be O(n).
Follow-up Questions
- What is the difference between amortized and average-case complexity?
- Why is geometric growth important?