Tempo amortizado da matriz dinâmica

Como um exemplo simples, em uma implementação específica da matriz dinâmica, dobramos o tamanho da matriz cada vez que ela é preenchida. Por isso, a realocação da matriz pode ser necessária e, no pior caso, uma inserção pode exigir O (n). No entanto, uma sequência de n inserções sempre pode ser feita em O (n) tempo, porque o restante das inserções são feitas em tempo constante, portanto, n inserções podem ser concluídas em O (n) tempo. O tempo amortizado por operação é, portanto, O (n) / n = O (1). --de Wiki

Mas em outro livro: Cada duplicação leva tempo O (n), mas acontece tão raramente que seu tempo amortizado ainda é O (1).

Espero que alguém possa me dizer que a rara situação infere a explicação do Wiki? obrigado

questionAnswers(2)

yourAnswerToTheQuestion