>> It's actually log n.

Actually, it is not!!

Most functions have constant complexity, except for push, which is O(n+ log(n)) = O(n).

Let me explain:

1. std::lower_bound is logarithmic in N -> O( log(N) )
2. vector<T>::insert is linear in the number of elements of the vector -> O(N)

vector<T>::insert is your bottleneck here:

* In the best case it will move all the elements at the right of the element being inserted. 
* In the worst case it will have to allocate a new array and the move ALL the elements to the new location.

Best regards
Juan



On Tue, Sep 27, 2016 at 4:14 PM, degski <degski@gmail.com> wrote:
On 27 September 2016 at 18:55, Oswin Krause <Oswin.Krause@ruhr-uni-bochum.de> wrote:
Your solution has linear complexity...
 
It's actually log n.

HAGD,

degski

_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users



--
Juan
:wq