Complexity of algorithm std::includes in c++

  • A+
Category:Languages

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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: