Какова временная сложность операции вставки элемента в контейнер std::vector?

Временная сложность вставки элемента в std::vector зависит от того, есть ли необходимость в перераспределении памяти:

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

Таким образом, вставка в std::vector обычно очень быстрая, но иногда может быть дорогой из-за перераспределения.