std::includes takes two sorted ranges and checks whether set2 is in set1 (i.e. if each element of set2 is included in set1)?
I wonder why eel.is/c++draft says that the complexity of this algorithm is at most
It seems to me that it should be only at most
2·N1 comparisons, with the worst case when
max(set2) >= max(set1).
I agree with your conclusion. The inteleaved sets example from Aki Suihkonen's answer is wrong because the algorithm will exit early as soon as
2 < 3.
The sample implementation on cppreference has a loop which increments
first1 on every iteration, returns when
first1 == last1, performs at most 2 comparisons per iteration, and contains no nested loops. I don't see how this could do more than