Какова сложность основных операций со списком Python?

Для Python list доступ по индексу — O(1), append и pop с конца — амортизированно O(1), вставка и удаление в середине — O(n). Поиск значения и проверка in также линейны.

Срез длины k требует O(k) времени и новой памяти, копирование всего списка — O(n). Extend имеет стоимость O(k) добавляемых элементов с учётом перераспределений; сортировка в худшем случае O(n log n). Амортизированное время означает среднюю стоимость длинной последовательности операций, а не гарантию каждого append. Оценки предполагают ограниченную стоимость сравнения и присваивания ссылок; пользовательский eq или key может добавить собственные затраты.