Какая алгоритмическая сложность вставки объекта в список в Python

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

Пример:

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

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