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_bound`

in the`algorithm`

package has no knowledge about the internal structure of`set`

. It can do a binary search for random access containers, but not for`set`

. For`set`

, it has to go through all elements step by step.On the other hand,

`set`

's`lower_bound`

can leverage its knowledge about its internal structure, and can do it log n runtime.One minor technical detail is that the

`lower_bound`

function from`algorithm`

actually always does a binary search.It's just that for forward iterators such as

`set::iterator`

that are not random access iterators`advance(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_bound`

on a container that only has forward iterators will usually be a bit slower than`find`

.)If only i had a nickle everytime I see lowerbound issue in set