You are not logged in. Please login at to post your questions!


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

I was solving this November Lunchtime 2017 problem: 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:

This is also mentioned in Complexity section of std::lower_bound() in cppreference website:

asked 30 Dec '17, 20:35

shubhambhattar's gravatar image

accept rate: 20%

edited 31 Dec '17, 01:09

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

dodobhoot's gravatar image

accept rate: 25%

Debugging better for this problem


answered 12 Jan, 18:42

sampath_001's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 30 Dec '17, 20:35

question was seen: 623 times

last updated: 12 Jan, 18:42