Complexity of algorithm std::includes in c++

Question

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).

Answer 1

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.