Computational complexity of STL algorithms and container methods
English
Advanced
In order to use STL correctly, you need to understand the computational complexity of STL algorithms and methods of STL containers. Besides, questions about computational complexity are often asked on job interviews. To pass this test you need to know: STL algorithms and data structures; what is big O notation (asymptotic notation) and what is O(1), O(n) and O(n*log (n)); what's the difference between average and worst case complexity. Next, we will assume that by default we are talking about STL containers consisting of n elements (container.size () == n) and only about computational complexity (time complexity). Any additional information will be explicitly mentioned in the question.
Description
35
Questions
1 min
Per question
2:13
Average time
4.2
Contest Score
10
Participants
4 comments
Bossy Puffin judge
This test may have a higher chance of receiving a reward. Nominated for:

1. Educational explanations. 👍 Explanations cover why the correct answers are correct.
E.g.: #q1, #q2, #q3 etc.

2. Step-by-step approach to teaching. 👍
Mindful Kitten
The last question suggests
```
What's the complexity of std::nth_element(first, nth, last), where last - first = n and nth - first = m?
```

The question suggests that the complexity is O(m) but that is not true because you cannot find the minimal element in an array with O(1) complexity. nth_element always works O(n) on average https://en.cppreference.com/w/cpp/algorithm/nth_element
Ace Cock author
Yeah you're right, my bad
Small Lizard
(The same mistake as in your Russian quiz)
What's the complexity of std::set_intersect for two sorted ranges of n and m elements?
Options O(max(n, m)) and O(n+m) are equal (because (n+m)/max(n, m)<=2), so they are both correct.
Take the quiz to leave a comment