Qual é a complexidade temporal da remoção de elementos de um vetor no pior caso?

No pior caso, remover elementos de um vetor (std::vector em C++) tem uma complexidade de tempo O(n), onde n é o número de elementos no vetor após a posição de remoção. Isso ocorre porque, após remover elementos, todos os elementos seguintes precisam ser deslocados para a esquerda para preencher o espaço vazio.

Por exemplo, se remover um elemento no início do vetor, todos os outros elementos precisam ser deslocados uma posição para frente, o que requer O(n) operações.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // remoção do primeiro elemento
// todos os elementos são deslocados uma posição para a esquerda

Se um elemento for removido no final, o deslocamento não é necessário, e a operação será mais próxima de O(1). Mas no pior caso — O(n).