Care este complexitatea temporală a eliminării elementelor dintr-un vector în cel mai rău caz?

În cel mai rău caz, eliminarea elementelor dintr-un vector (std::vector în C++) are o complexitate temporară de O(n), unde n este numărul de elemente din vector după poziția de eliminare. Acest lucru se datorează faptului că, după eliminarea elementelor, toate elementele următoare trebuie mutate spre stânga pentru a umple spațiul gol.

De exemplu, dacă se elimină un element de la începutul vectorului, toate celelalte elemente trebuie mutate cu o poziție înainte, ceea ce necesită O(n) operații.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // eliminarea primului element
// toate elementele sunt mutate cu o poziție spre stânga

Dacă se elimină un element de la sfârșit, nu este nevoie de mutare, iar operația va fi mai aproape de O(1). Dar în cel mai rău caz — O(n).