Why does a dynamic array such as C++ std::vector achieve amortised O(1) time for appending elements?
Correct answer C. It grows its capacity geometrically, so expensive reallocations happen rarely
Explanation
When a vector runs out of room it allocates a larger block, typically a constant multiple of the old size, and copies the elements across. That copy is O(n), but because capacity multiplies, such copies become rarer as the array grows, and the total cost over n appends is O(n). Spread out, each append costs O(1) on average.
Answer checked How we write and check questions
Discussion