Junior
What is the asymptotic complexity of a list container?
sobes.tech AI
Answer from AI
- Index access (operator
[]) - O(n) - Insertion at the beginning (
push_front) - O(1) - Insertion at the end (
push_back) - O(1) - Insertion in the middle (by iterator) - O(1)
- Removal from the beginning (
pop_front) - O(1) - Removal from the end (
pop_back) - O(1) - Removal by iterator - O(1)
- Element search (
find) - O(n) - Sorting (
sort) - O(n log n) - Size (
size) - O(n) (ifstd::listdoes not explicitly track size, in C++11 this is O(1) for most implementations).