Algorithms and Data Structures · Junior · Question 63 of 75
What does "amortized O(1)" mean for arr.push?
- 1Every single push is guaranteed to take the same time
- ✓Correct answer: Rare O(n) resizes average out to O(1) per push
- 3The push is O(1) only for arrays shorter than 1,000
Explanation
When the internal buffer is full, the array allocates a bigger one (usually about double) and copies everything. Because the size doubles, these copies are rare, and the total cost of n pushes is O(n).