Time Complexity of lower_bound

Правка en1, от teja349, 2016-12-02 22:47:52

I have observed a fact while solving 760D - Travel Card. 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); ~~~~~ here is my submission in which it took O(logn) when i used in above format[submission:22663799]
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[submission:22663731]
[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

Теги lower_bound

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский teja349 2016-12-02 22:54:35 194
en2 Английский teja349 2016-12-02 22:48:25 0 (published)
en1 Английский teja349 2016-12-02 22:47:52 941 Initial revision (saved to drafts)