Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Cache's blog

By Cache, history, 4 years ago, In English,

I have observed a fact while solving . The complexity of lower bound varies with type of iterator passed to it.

But a more weird fact is
1. the below lower bound takes O(log(n)) time
~~~~~ multiset< ll > set1; //some insert operation on multiset it=set1.lower_bound(val); ~~~~~

the question is Vasiliy's Multiset

here is my submission in which it took O(logn) when i used in above format here
2. the below lower bound works in O(n) time

multiset< ll > set1;
//some insert operation on multiset
it=lower_bound(set1.begin(),set1.end(),val);

here is my submission in which it took O(n) when i used in above format here
[cut] I dont understand why it was happening like this because both iterators here are same type.

Can someone specify places where all places lower_bound function is of O(logn) complexity

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).

»
4 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

set::lower_bound takes advantage of knowing it's applying this operation on a set and it's properties. Ensuring logN time.

While std::lower_bound only promises logN time if the iterators are random. Set iterator is a not a random one ( as far as I know, I don't mainly use C++), so that explains the time.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think even u solved it the same way and got TLE right

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Method lower_bound of std::multiset class works with internal implementation, it searches for the suitable vertix in self-balanced tree.

And function std::lower_bound uses usual binary search which requires random access iterators for checking element inside range using O(1) time.

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Just change it to

it=set1.lower_bound(val);

This is strictly O(log(n))

»
3 weeks ago, # |
  Vote: I like it -46 Vote: I do not like it

how can I implement lower bound on vector pair in logn

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    I tried this,but still getting error.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I assume you mean that you have something like, vector<pair<int, int>> which is sorted by the standard comparator and you want to do a lower_bound call but only on the first coordinate. If, say, you want to get the first element that is of the form {4, x}, then you should do a lower_bound call with the value {4, INT_MIN} or whatever the corresponding minimum is. Note that this will be a different value if you are not using the standard comparator.