Como é determinada a complexidade temporal da operação de inserir um elemento no final de um vetor padrão em C++?

A complexidade temporal de inserir um elemento no final de um vetor padrão (std::vector) em C++ é geralmente amortizada constante, ou seja, O(1) em média. Isto deve-se ao fato de que o vetor aloca memória com reserva, e ao adicionar um elemento, se o buffer atual não estiver cheio, a inserção é rápida — simplesmente copia ou move o elemento.

No entanto, quando o buffer interno do vetor está cheio, ocorre uma realocação de memória: um novo buffer de maior tamanho (normalmente o dobro) é alocado, todos os elementos são copiados ou movidos para o novo buffer, e o antigo é liberado. Esta operação leva tempo O(n), onde n é a quantidade atual de elementos.

Porém, como essas realocações não acontecem a cada inserção, mas apenas periodicamente, a complexidade amortizada de inserir no final permanece O(1).

Exemplo:

std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // amortizado O(1)
}