I was attempting the following question 310D
Here is my submission that timed-out TLE
And here is my submission that was accepted AC
As you may have observed, the only change I made from the TLE code to AC code was
it=lower_bound(s.begin(),s.end(),mp(lo,o));
to
it=s.lower_bound(mp(lo,o));
where "it" is a set iterator.
Just changing this, the time on Test #11 was reduced from >3000ms to 264ms. Can any one shed some light on why this happened? Thank you.
I think without be sure that the first runs in 0(N), and the second in O(logN).
Okay. But why the change in behaviour for the same function? I mean what goes behind the curtains?
See complexity of these methods 1 2
Thanks a lot. Glad I got to know this now, getting TLE in a contest because of this would have hurt.
Actually you will find everything about C++ in this site. So, you can always check anything there.
http://www.cplusplus.com/
The key is, that the
lower_boundin thealgorithmpackage has no knowledge about the internal structure ofset. It can do a binary search for random access containers, but not forset. Forset, it has to go through all elements step by step.On the other hand,
set'slower_boundcan leverage its knowledge about its internal structure, and can do it log n runtime.One minor technical detail is that the
lower_boundfunction fromalgorithmactually always does a binary search.It's just that for forward iterators such as
set::iteratorthat are not random access iteratorsadvance(iterator,constant)is slow. More precisely, you need roughly k operations to advance an iterator by k, and this is what makes the total time complexity linear instead of logarithmic.(Hence,
lower_boundon a container that only has forward iterators will usually be a bit slower thanfind.)