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