Блог пользователя harshit2202

Different time complexities in multiset lower_bound
Автор harshit2202, история, 6 лет назад, По-английски

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??

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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.

→ Ответить