- A+

The algorithm `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 `2·(N1+N2-1)`

comparisons?

The same is stated at:

1. cppreference

2. cplusplus

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 `2xN1`

comparisons.