Amortized time of dynamic array

问题:

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, because the rest of the insertions are done in constant time, so n insertions can be completed in O(n) time. The amortized time per operation is therefore O(n) / n = O(1). --from Wiki

But in another book :Each doubling takes O(n) time, but happens so rarely that its amortized time is still O(1).

Hope somebody could tell me does the rare situation infer the Wiki explanation? Thanks

回答1:

Amortized basically means average per number of operations.

So, if you have an array of n, you need to insert n+1 items until you'll need the reallocation.

So, you've done n inserts which each one of them took O(1), and another insert that took O(n), so in total you've got n+1 actions that cost you 2n operations .

2n / n+1  ~= 1 

That's why the Amortized time is still O(1)

回答2:

Yes, these two statements say the same thing, Wiki just explains it more thoroughly.