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

Вставка элемента в нулевую позицию списка (list) в Python имеет сложность O(n), так как требует сдвига всех остальных элементов списка на одну позицию вправо. Это связано с тем, что списки в Python реализованы как динамические массивы.

Пример:

my_list = [1, 2, 3]
my_list.insert(0, 0)  # O(n)
# После вставки: [0, 1, 2, 3]

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

from collections import deque
d = deque([1, 2, 3])
d.appendleft(0)  # O(1)