Некоторые операции в большинстве случаев дешёвые и лишь изредка дорогие. Если применять худший случай к каждой операции отдельно, оценка получается слишком пессимистичной. Амортизированный анализ берёт суммарную стоимость последовательности операций и делит её на их число.

Стоимость каждого append: большинство по 1, несколько по 2, 3, 5, 9; среднее около 2
Стоимость каждого append: большинство по 1, несколько по 2, 3, 5, 9; среднее около 2

Динамический массив: list.append

Список хранится в массиве. Когда место кончается, выделяется новый, больший массив и все элементы копируются — это O(n). Но если каждый раз увеличивать ёмкость вдвое, копирования происходят редко: 1 + 2 + 4 + ... + n/2 < n. Общая стоимость n добавлений: n (сами добавления) + < n (копирование) = O(n), то есть один append стоит амортизированно O(1).

python
class DynArray:
    def __init__(self):
        self.cap = 1
        self.size = 0
        self.data = [None]
        self.copies = 0