Qual é a complexidade da operação push_back em std::vector?

Em média, a amortização é O(1).

No pior caso, O(N), onde N é o tamanho atual do vetor. Isso ocorre durante a realocação de memória, quando a capacidade atual do vetor não é suficiente para um novo elemento. Nesse momento, um novo buffer de maior capacidade é criado, os elementos são copiados para lá, e o buffer antigo é liberado.