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

Средно amortизацията е O(1).

В най-лошия случай, O(N), където N е текущият размер на вектора. Това се случва при преразпределение на паметта, когато текущата капацитет на вектора не е достатъчен за нов елемент. В този момент се създава нов буфер с по-голяма капацитет, елементите се копират там, а старият буфер се освобождава.