I have observed a fact while solving [problem:760D]. The complexity of lower bound varies with type of iterator passed to it.<br>↵
↵
But a more weird fact is <br>↵
1. the below lower bound takes O(log(n)) time <br>↵
~~~~~↵
multiset< ll > set1;↵
//some insert operation on multiset↵
it=set1.lower_bound(val);↵
~~~~~↵
here is my submission in which it took O(logn) when i used in above format[submission:22663799]<br>↵
[cut]↵
↵
2. the below lower bound works in O(n) time<br>↵
↵
~~~~~↵
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[submission:22663731]<br>↵
[cut]↵
I dont understand why it was happening like this because both iterators here are same type.<br>↵
↵
Can someone specify places where all places lower_bound function is of O(logn) complexity<br>↵
↵
↵
↵
↵
↵
↵
↵
↵
But a more weird fact is <br>↵
1. the below lower bound takes O(log(n)) time <br>↵
~~~~~↵
multiset< ll > set1;↵
//some insert operation on multiset↵
it=set1.lower_bound(val);↵
~~~~~↵
here is my submission in which it took O(logn) when i used in above format[submission:22663799]<br>↵
[cut]↵
↵
2. the below lower bound works in O(n) time<br>↵
↵
~~~~~↵
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[submission:22663731]<br>↵
[cut]↵
I dont understand why it was happening like this because both iterators here are same type.<br>↵
↵
Can someone specify places where all places lower_bound function is of O(logn) complexity<br>↵
↵
↵
↵
↵
↵
↵
↵
