the_stone_dawg's blog

Runtime difference of using std::upper_bound on different underlying data structures?

By the_stone_dawg, history, 3 years ago, In English

Hi there, while working on this problem, I ran into a situation where using std::upper_bound(set) TLE'd, while replacing the set with a sorted array was comfortably within the time constraints. (TLE submission: 145179964, AC: 145179970). AFAIK, these two should be equivalent O(log n), up to constants. In practice, is it just that those constant factors are great enough to TLE solutions that are asymptotically within the constraint, or is there something else I'm missing when using std::upper_bound with sets instead of vectors?

Thanks!

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

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

AFAIK, these two should be equivalent O(log n), up to constant

That's probably incorrect. From the information I get, when applying to std::set, the time complexity of std::upper_bound will degenerate because it doesn't have random access iterator. Instead, member function upper_bound of std::set has a time complexity of $$$O(log\;n)$$$ and it might work with you solution.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

No, std::upper_bound works with binary search approach in the sorted array (O(logN)) while in sets/maps doesn't iterate through Binary search (IDK the exact way), but it works in O(N) time.

Instead, you can use it this way.

set_name.lower_bound(value); it works in O(log N)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

set::upper_bound

→ Reply