Амортизированная константа

Ну вот смотрите. Берем динамическим массив. Сначала из одного элемента.

Добавляем еще один. Удваиваем массив. Итого - одно выделение, один перенос (первого элемента).

Еще добавление - массив становится равен 4 элементам. Выделений - 2. переносов - 3 (теперь переносим 2 элемента, + 1 ранее). Добавление четвертого элемента не требует ни выделения, ни переноса.

Еще добавление. Массив увеличивается до 8 элементов. Теперь в массиве 8 элементов, 3 выделения памяти, 7 переносов элементов. Элементы с 6 по 8 не требуют ни выделения, ни переноса...

...

Теперь у нас 2n элементов, n выделений памяти, 2n-1 переноса элементов.

Т.е. в среднем каждый элемент пришлось переносить 1-2-n раз, при больших n - 1 раз.

Константа? Да. При том, что первый элемент переносился log2n раз.

А вот в среднем, т.е. амортизированно - константа.

Так более-менее понятно?