What does O(log n) mean exactly?

Posted by Andreas Grech on Stack Overflow See other posts from Stack Overflow or by Andreas Grech
Published on 2010-02-21T20:05:38Z Indexed on 2010/03/19 19:31 UTC
Read the original article Hit count: 320

Filed under:
|
|
|

I am currently learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportionally...and the same goes for, for example, quadratic time O(n2) etc..even algorithms, such as permutation generators, with O(n!) times, that grow by factorials.

For example, the following function is O(n) because the algorithm grows in proportion to its input n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Similarly, if there was a nested loop, the time would be O(n2).

But what exactly is O(log n)? For example, what does it mean to say that the height of a complete binary tree is O(log n)?

I do know (maybe not in great detail) what Logarithm is, in the sense that: log10 100 = 2, but I cannot understand how to identify a function with a logarithmic time.

© Stack Overflow or respective owner

Related posts about big-o

Related posts about algorithm