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