Jaka jest złożoność operacji push_back w std::vector?

Średnio amortyzacja wynosi O(1).

W najgorszym przypadku O(N), gdzie N to aktualny rozmiar wektora. Dzieje się tak podczas ponownej alokacji pamięci, gdy obecna pojemność wektora jest niewystarczająca dla nowego elementu. W tym momencie tworzony jest nowy bufor o większej pojemności, elementy są kopiowane tam, a stary bufor jest zwalniany.