Каква е времевата сложност на операцията по изтриване на елементи от вектор в най-лошия случай?

В най-лошия случай изтриването на елементи от вектор (std::vector в C++) има времева сложност O(n), където n е броят на елементите във вектора след позицията на изтриване. Това се дължи на факта, че след изтриването на елементите, всички следващи елементи трябва да бъдат преместени наляво, за да запълнят образувалата се празнина.

Например, ако изтриете елемент в началото на вектора, всички останали елементи трябва да бъдат преместени с една позиция напред, което изисква O(n) операции.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // изтриване на първия елемент
// всички елементи се преместят с една позиция наляво

Ако се изтрие елемент в края, преместване не е необходимо, и операцията ще бъде по-близо до O(1). Но в най-лошия случай — O(n).