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

Tags

35

Questions

1 min

Per question

2:43

Average time

4.2

Contest Score

12

Participants

1. Educational explanations.

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

2. Step-by-step approach to teaching.

👍```

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

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.