Time Complexity of std::lower_bound() vs container::lower_bound() is NOT ALWAYS SAME!

I was solving this November Lunchtime 2017 problem: https://www.codechef.com/problems/LRQUER and after getting a lot of TLEs, I learned the following:

std::lower_bound(<container>.begin(), <container>.end(), query) and <container>.lower_bound(query) does not always have the same time complexity.

To be specific, in containers that support Random Access Iterators (std::vector, std::array, etc.), they’ll have the same time complexity but not if the container don’t support them (std::set, etc.). I was using std::multiset in my solution.

Please read this comment in Codeforces to learn more: http://codeforces.com/blog/entry/20553?#comment-252670

This is also mentioned in Complexity section of std::lower_bound() in cppreference website: http://en.cppreference.com/w/cpp/algorithm/lower_bound

5 Likes

This is something that we usually overlook while studying complexity of a function. Thanks for pointing this out. Saved a lot of future debugging.

1 Like

Debugging better for this problem