Какая алгоритмическая сложность вставки значений в конец списка

Вставка элемента в конец списка (list.append()) в Python имеет амортизированную сложность O(1).

Хотя иногда при расширении списка требуется переаллокация памяти (копирование в новый участок), Python использует стратегию динамического увеличения размера (обычно в ~1.125–2 раза), что делает среднюю стоимость операции константной.

Пример:

lst = [1, 2, 3]
lst.append(4)  # O(1)

Исключение: если список создан с фиксированным размером (array.array или numpy.ndarray), вставка может потребовать O(n) из-за копирования.