Qual è la complessità temporale dell'eliminazione di elementi da un vettore nel caso peggiore?

Nel caso peggiore, rimuovere elementi da un vettore (std::vector in C++) ha una complessità temporale di O(n), dove n è il numero di elementi nel vettore dopo la posizione di rimozione. Ciò è dovuto al fatto che, dopo aver rimosso gli elementi, tutti gli elementi successivi devono essere spostati a sinistra per riempire lo spazio vuoto.

Ad esempio, se si rimuove un elemento all'inizio del vettore, tutti gli altri elementi devono essere spostati di una posizione in avanti, il che richiede O(n) operazioni.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // rimozione del primo elemento
// tutti gli elementi vengono spostati di una posizione a sinistra

Se si rimuove un elemento alla fine, non è necessario spostare nulla, e l'operazione sarà più vicina a O(1). Ma nel caso peggiore — O(n).