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

http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o :) — Skurmedel, Feb 08 '11 at 15:36
The tag @aschepler added gives it a name, so now you can find the numerous questions explaining it ;) See http://stackoverflow.com/questions/tagged/big-o?sort=votes. (Someone pick one and cast a vote so I don't have to decide...) — , Feb 08 '11 at 15:37
For the second part of your question: http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers — Skurmedel, Feb 08 '11 at 15:38

Motti · Accepted Answer · 2011-02-08T15:55:39.460

6

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

edited Feb 08 '11 at 15:55

answered Feb 08 '11 at 15:36

Motti

110,860
49
189
262

Technically it's not a measurement but a calculation – Falmarri Feb 08 '11 at 15:37
Not performance. Complexity, i.e. how well it scales. And big O is strictly speaking "only" for the upper bound/worst case. – Feb 08 '11 at 15:38
@delnan, saying _complexity_ to someone who doesn't know what `O(n)` means is sort of like telling someone that to understand recursion they must first understand recursion. – Motti Feb 08 '11 at 15:40
Along with an explanation of it, of course (even I, in my puny comment, provided a small one). Saying "performance" to them is like telling them a CPU's clock rate determines how fast numbers are crunched. – Feb 08 '11 at 15:46
1

@delnan: _Worst case_ and _upper bound_ are seperate concepts. You can do big-O calculations also for the average case, but it's always an upper bound - anything that is `O(n)` is also `O(n^2)`, also something that is `O(n)` might be `O(lg(n))`, but it doesn't have to. – etarion Feb 08 '11 at 15:58

score 5 · Answer 2 · answered Feb 08 '11 at 15:36

Big-O notation is about the time complexity of a programs performance.

so O(ln(n)) means that accessing elements in std::vector as the vector gets larger is proportional to ln(size_of_vector), but this is only with a sorted vector using binary search. Binary search performs faster than linear search because you eliminate possible elements twice as fast, thus the ln is really a log base 2.

http://en.wikipedia.org/wiki/Big_O_notation

score 5 · Answer 3 · edited Feb 08 '11 at 16:42

This is known as the Big O notation, it is an expression of the asymptotic complexity of a given algorithm and in relation with some parameters.

asymptotic means that we are not interested in the first few cases, but about the behavior of the algorithm when the size of the input parameters grow.
the parameters depend on the algorithm to be measured
an operation in which we are interested

For example, in the case of a binary search we express a relationship between the number of comparison performed depending on the size of the set in which we search.

The running time can usually be inferred from this, but it is not always true, especially if one didn't picked up the right "operation" with regard to the implementation or hardware constraints.

There was a nice post a few days ago speaking about sorting using a tape as storage. Because the complexities in searching express the number of comparison and using a tape as storage the runtime is mostly affected by the movement of the tape... it turned out that bubblesort would perform better than quicksort despite being described as slower in general.

score 4 · Answer 4 · answered Feb 08 '11 at 15:36

4

The O is big O notation. It describes the runtime complexity of an algorithm. Essentially it's the number of operations required to compute the answer.

answered Feb 08 '11 at 15:36

Falmarri

47,727
41
151
191

it does not have to be run time - big O can refer to any computing resource e.g. memory – jk. Feb 08 '11 at 16:38

score 2 · Answer 5 · answered Feb 08 '11 at 15:39

2

All the other answers have cleared up O, to find the typical complexity of a given algorithm look at a decent reference, such as this. At the bottom of each algorithm, the complexity of the algorithm is documented.

answered Feb 08 '11 at 15:39

Nim

33,299
2
62
101

score 1 · Answer 6 · answered Feb 08 '11 at 15:36

1

O is an abbreviation for "Order". It's a measure of the running time of the operation.

For example, this code is O(n^2) because it's going to execute n*n times.

int n = 100;
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
  }
}

answered Feb 08 '11 at 15:36

dcp

54,410
22
144
164

STL performance O(ln(n)) questions

6 Answers6