Amortized time of a dynamic array

Question

As a simple example, in a specific implementation of a dynamic array, we increase the size of the array each time. Because of this, array redistribution may be required, and in the worst case, O (n) may be required for insertion. However, a sequence of n inserts can always be performed at O ​​(n) time, since the remaining inserts are performed at constant time, so n attachments can be completed at O ​​(n) time. Thus, the amortized time for the operation is O (n) / n = O (1). - from Wiki

But in another book: each doubling takes O (n) time, but it is so rare that its amortized time is still O (1).

Hope someone can tell me that a rare situation brings out Vicki's explanation? Thanks

Answer 1

Depreciation basically means the average number of transactions.

So, if you have an array of n, you need to insert n + 1 elements until you need redistribution.

So, you made n inserts that each of them took O (1) , and the other insert that took O (n) , so in the end you have n + 1 actions that cost you 2n operations .

2n / n+1 ~= 1 

So why amortized time is still O (1)

Answer 2

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