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

Вставка элемента в середину списка (list) в Python имеет временную сложность O(n), где n — длина списка.

Причина:

• Списки в Python реализованы как динамические массивы.
• При вставке элемента в произвольную позицию все последующие элементы сдвигаются вправо.

Пример:

lst = [1, 2, 3, 4, 5]
lst.insert(2, 99)  # O(n), сдвигает элементы 3,4,5
print(lst)  # [1, 2, 99, 3, 4, 5]

Если требуется частая вставка в середину, лучше использовать collections.deque (если вставка ближе к краям) или другие структуры данных (например, связные списки через list эмуляцию или сторонние библиотеки).