Milline on elementide eemaldamise operatsiooni ajakulu vektoris kõige halvemal juhul?

Halvim juhul on vektori (C++-s std::vector) elementide eemaldamine ajakulu O(n), kus n on eemalduspositsiooni järgsed elementide arv vektoris. See tuleneb sellest, et pärast elementide eemaldamist tuleb kõik järgnevad elemendid vasakule nihutada, et täita tekkinud tühi ruum.

Näiteks, kui eemaldame elemendi vektori algusest, tuleb kõiki teisi elemente nihutada ühe positsiooni ettepoole, mis nõuab O(n) operatsiooni.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // esimese elemendi eemaldamine
// kõik elemendid nihkuvad ühe positsiooni vasakule

Kui eemaldame viimase elemendi, pole nihutamine vajalik, ja operatsioon on lähemal O(1)-le. Kuid halvimatel juhtudel — O(n).