Qual è la complessità dell'operazione push_back in std::vector?

In media, l'amortamento è O(1).

Nel caso peggiore, O(N), dove N è la dimensione attuale del vettore. Questo accade durante la riallocazione della memoria, quando la capacità attuale del vettore non è sufficiente per un nuovo elemento. In quel momento, viene creato un nuovo buffer con capacità maggiore, gli elementi vengono copiati lì e il buffer vecchio viene liberato.