harshit2202's blog

Different time complexities in multiset lower_bound
By harshit2202, history, 5 years ago, In English

I recently found that s.lower_bound(val) and lower_bound(s.begin(),s.end(),val) have varying time complexities.

Submission-1: (which gave TLE) Sub-1 Submission-2: (got AC) Sub-2

Both submission differ only in lower_bound line. Reasons for varying complexities??

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Because the first one is O(n) per lower_bound and the second one is O(logn). This is because a set or a multiset is not indexed and the lower_bound has to use a iterator to increase one by one to move to the the desired position to check. Please Refer to the Documentation for further details.

→ Reply