STL performance O(ln(n)) questions

Question

Please, can someone explaine this:

If documentations says that STL std::vector finding element speed performace = O(ln(n)), what does it mean.

O(ln(n)) - what is "O", where I can read about that?

And where I can read about performace of other STL containers preformance

Thank you very much

Answer 1

Big O notation is a way to measure how an algorithm will scale as the size of the data on which it is working grows.

Finding an element if a vector is usually O(n), it's only O(lg(n)) when the vector is sorted and you use one of the binary search family of algorithms.

The complexity of each algorithm is specified in the standard and also in any reference (such as the above link to std::lower_bound).

BTW, ln is log on base e, but all logarithms are the same complexity so even though a binary search only performs lg (log₂) operations it's technically correct to say it's O(ln(n)).