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