> Какова алгоритмическая сложность добавления элемента в начало и конец списка в Python (Python)

Добавление элемента в конец списка (метод append) работает в среднем за O(1) - амортизированная константа. Это достигается за счёт того, что список хранит элементы в динамическом массиве: при заполнении выделяется больший блок памяти (обычно с запасом ~12.5%), и копирование происходит редко.

Добавление элемента в начало списка (например, list.insert(0, x)) работает за O(n), где n - длина списка. Все существующие элементы сдвигаются на одну позицию вправо, что требует линейного количества операций копирования.

Пример:

PYTHON
lst = [1, 2, 3]
lst.append(4)          # O(1) - быстро
lst.insert(0, 0)       # O(n) - медленно на больших списках

Поэтому для частых вставок в начало лучше использовать collections.deque, у которого вставка в начало и конец - O(1).