¿Cuál es la complejidad de la operación push_back en std::vector?

En promedio, la amortización es O(1).

En el peor caso, O(N), donde N es el tamaño actual del vector. Esto ocurre durante la reasignación de memoria, cuando la capacidad actual del vector no es suficiente para un nuevo elemento. En ese momento, se crea un nuevo búfer con mayor capacidad, los elementos se copian allí y el búfer antiguo se libera.