Каква е времевата сложност на операцията по вмъкване на елемент в динамичен масив тип vector в най-лошия и средния случай?

В динамическом массиве типа vector в C++ операция вставки элемента имеет:

• Среднюю временную сложность O(1) — когда есть свободное место в выделённой памяти, элемент просто добавляется в конец.
• Худшую временную сложность O(n) — когда выделённая память заполнена, происходит перераспределение (реаллоцирование) памяти: выделяется новый блок большего размера, все существующие элементы копируются в новый блок, и затем добавляется новый элемент.

Таким образом, несмотря на редкие дорогостоящие операции копирования, амортизированная сложность вставки остаётся O(1).