Что такое amortized complexity?

Amortized complexity — средняя стоимость операции за серию вызовов. Пример: append к slice в Go — обычно O(1), но иногда O(n) когда нужно расширение (выделяется новый массив, копируются данные). Но расширение происходит редко (capacity удваивается), поэтому amortized complexity — O(1). Это не average case (средний по входам), а гарантированная средняя стоимость по серии операций. Аналогично: вставка в хеш-таблицу — amortized O(1), хотя рехеширование стоит O(n).