Какова сложность операции push_back у std::vector?

В среднем амортизированно O(1).

В худшем случае O(N), где N — текущий размер вектора. Это происходит при перевыделении памяти, когда текущая емкость вектора недостаточна для нового элемента. При этом создается новый буфер большей емкости, элементы копируются туда, а старый буфер освобождается.