Wat is de tijdcomplexiteit van het verwijderen van elementen uit een vector in het slechtste geval?

In het slechtste geval heeft het verwijderen van elementen uit een vector (std::vector in C++) een tijdcomplexiteit van O(n), waarbij n het aantal elementen in de vector na de verwijzingspositie is. Dit komt doordat na het verwijderen van elementen alle volgende elementen naar links moeten worden verschoven om de lege ruimte op te vullen.

Bijvoorbeeld, als een element aan het begin van de vector wordt verwijderd, moeten alle andere elementen één positie naar voren worden verschoven, wat O(n) bewerkingen vereist.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // verwijderen van het eerste element
// alle elementen verschuiven één positie naar links

Als een element aan het einde wordt verwijderd, is verschuiven niet nodig, en zal de operatie dichter bij O(1) liggen. Maar in het slechtste geval — O(n).