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

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

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

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