Complexity of insertion

Question

I have a sorted vector, what is better: using lower_bound and insert the element at its place in the vector. or simply push_back the element into vector and sort it when it is required with sort()?

Answer 1

For that individual operation performed once, it is cheaper to use lower_bound and insert. lower_bound is O(log(n)) and insert will be (worst and average case) O(n), giving a final complexity of O(n).

If you don't need the vector sorted until after you're done inserting into it, it will be much cheaper to sort only once, since all the push_backs will be O(1)*O(n) = O(n) and the final sort will be O(n*log(n)), giving you a final complexity of O(n*log(n)), whereas the multiple lower_bound+insert will give you a complexity of O(n)*O(n) = O(n**2).

If you need the elements sorted throughout the insertion process, which one is cheaper will depend heavily on your usage pattern (how often and when you need the elements sorted). It can often be the case that you only need the elements sorted at the end of the construction process, which is why sorting at the end can be a very powerful tool in your tool belt. If that is not your usage pattern, you may want to at least consider using an associative container such as multi_set or multi_map.