You are not logged in. Please login at www.codechef.com 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: 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

asked 30 Dec '17, 20:35

shubhambhattar's gravatar image

3★shubhambhattar
1936
accept rate: 11%

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.

link

answered 30 Dec '17, 22:00

dodobhoot's gravatar image

5★dodobhoot
212
accept rate: 0%

Debugging better for this problem

link

answered 12 Jan, 18:42

sampath_001's gravatar image

0★sampath_001
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×231
×65
×33
×29
×10

question asked: 30 Dec '17, 20:35

question was seen: 530 times

last updated: 12 Jan, 18:42