Aká je časová zložitosť operácie odstránenia prvkov z vektora v najhoršom prípade?

V najhoršom prípade má odstraňovanie prvkov z vektora (std::vector v C++) časovú zložitosť O(n), kde n je počet prvkov vo vektore po pozícii odstránenia. To je spôsobené tým, že po odstránení prvkov je potrebné všetky nasledujúce prvky posunúť doľava, aby sa zaplnil vzniknutý voľný priestor.

Napríklad, ak odstránime prvok na začiatku vektora, všetky ostatné prvky je potrebné posunúť o jedno miesto dopredu, čo vyžaduje O(n) operácií.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // odstránenie prvého prvku
// všetky prvky sa posunú o jedno miesto doľava

Ak je odstránený prvok na konci, nie je potrebné posunúť, a operácia bude bližšie k O(1). Ale v najhoršom prípade — O(n).