Multiple choice technology programming languages

What is time complexity of Insertions or deletions at positions other than the end in "vector STL template class"

  1. O(1)

  2. O(N2)

  3. O(log N)

  4. O(N)
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Vector insertions or deletions at arbitrary positions require shifting all subsequent elements to maintain contiguous storage. In the worst case, this means moving N-1 elements, resulting in O(N) time complexity.

AI explanation

std::vector stores elements contiguously in memory. Inserting or erasing at any position other than the end requires shifting every element after that position by one slot to keep the array contiguous, which takes time proportional to the number of elements from that point to the end — O(N) in the worst/average case. Only insertion/removal at the very end (push_back/pop_back) is O(1) amortized. O(N^2) would be the cost of N such operations done naively, not a single one, and O(log N) is characteristic of tree/heap structures, not a contiguous vector, so those are wrong.

Keep practicing — related questions