Junior
What is the asymptotic complexity of insert and delete operations in list and vector containers?
sobes.tech AI
Answer from AI
std::vector:
| Operation | Asymptotic Complexity | Notes |
|---|---|---|
| Insertion | O(N) in the worst case | Requires shifting all subsequent elements. |
Insertion at the end (push_back) |
Amortized O(1) | May require memory reallocation O(N). |
| Deletion | O(N) in the worst case | Requires shifting all subsequent elements. |
Deletion from the end (pop_back) |
O(1) | Does not require shifts. |
std::list:
| Operation | Asymptotic Complexity | Notes |
|---|---|---|
| Insertion | O(1) | Only requires pointer changes. |
| Deletion | O(1) | Only requires pointer changes. |