×

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

 5 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(.begin(), .end(), query) and .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 asked 30 Dec '17, 20:35 288●7 accept rate: 23%

 1 This is something that we usually overlook while studying complexity of a function. Thanks for pointing this out. Saved a lot of future debugging. answered 30 Dec '17, 22:00 56●2 accept rate: 20%
 0 Debugging better for this problem answered 12 Jan, 18:42 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×277
×80
×80
×47
×10

question asked: 30 Dec '17, 20:35

question was seen: 925 times

last updated: 12 Jan, 18:42