Какова временная сложность операции удаления элемента из списка в Python?

В Python списки реализованы как динамические массивы. Операция удаления элемента из списка имеет разную временную сложность в зависимости от способа удаления и позиции элемента:

• list.pop() без аргументов удаляет последний элемент — это операция O(1), так как не требует сдвига элементов.
• list.pop(i) или del list[i] удаляет элемент по индексу i. В этом случае все элементы справа от i сдвигаются на одну позицию влево, поэтому операция занимает O(n - i), где n — длина списка.
• list.remove(value) ищет первый элемент со значением value и удаляет его. Поиск — O(n), удаление — как выше, итого O(n).

Таким образом, в худшем случае (удаление из начала списка) операция удаления — O(n), а в лучшем (удаление с конца) — O(1).