¿Cuál es la complejidad temporal de eliminar elementos de un vector en el peor caso?

En el peor caso, eliminar elementos de un vector (std::vector en C++) tiene una complejidad temporal de O(n), donde n es la cantidad de elementos en el vector después de la posición de eliminación. Esto se debe a que, después de eliminar elementos, todos los elementos siguientes deben desplazarse hacia la izquierda para llenar el espacio vacío.

Por ejemplo, si se elimina un elemento al principio del vector, todos los demás elementos deben desplazarse una posición hacia adelante, lo que requiere O(n) operaciones.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // eliminación del primer elemento
// todos los elementos se desplazan una posición hacia la izquierda

Si se elimina un elemento al final, no es necesario desplazar, y la operación será más cercana a O(1). Pero en el peor caso, — O(n).