What does O(log n) mean exactly?

Question

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(n²) 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(n²).

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: log₁₀ 100 = 2, but I cannot understand how to identify a function with a logarithmic time.

Answer 1

If you had a function that takes:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Then it takes log₂(n) time. The Big O notation, loosely speaking, means that the relationship only needs to be true for large n, and that constant factors and smaller terms can be ignored.

Answer 2

If you plot a logarithmic function on a graphical calculator or something similar, you'll see that it rises really slowly -- even more slowly than a linear function.

This is why algorithms with a logarithmic time complexity are highly sought after: even for really big n (let's say n = 10^8, for example), they perform more than acceptably.

Answer 3

Every time we write an algorithm or code we try to analyze its asymptotic complexity. It is different from its time complexity.

Asymptotic complexity is the behavior of execution time of an algorithm while the time complexity is the actual execution time. But some people use these terms interchangeably.

Because time complexity depends on various parameters viz.
1. Physical System
2. Programming Language
3. coding Style
4. And much more ......

The actual execution time is not a good measure for analysis.

Instead we take input size as the parameter because whatever the code is, the input is same. So the execution time is a function of input size.

Following is an example of Linear Time Algorithm

Linear Search
Given n input elements, to search an element in the array you need at most 'n' comparisons. In other words, no matter what programming language you use, what coding style you prefer, on what system you execute it. In the worst case scenario it requires only n comparisons.The execution time is linearly proportional to the input size.

And its not just search, whatever may be the work (increment, compare or any operation) its a function of input size.

So when you say any algorithm is O(log n) it means the execution time is log times the input size n.

As the input size increases the work done(here the execution time) increases.(Hence proportionality)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

See as the input size increased the work done is increased and it is independent of any machine. And if you try to find out the value of units of work It's actually dependent onto those above specified parameters.It will change according to the systems and all.

Answer 4

Simply put: At each step of your algorithm you can cut the work in half. (Asymptotically equivalent to third, fourth, ...)

Answer 5

Actually, if you have a list of n elements, and create a binary tree from that list (like in the divide and conquer algorithm), you will keep dividing by 2 until you reach lists of size 1 (the leaves).

At the first step, you divide by 2. You then have 2 lists (2^1), you divide each by 2, so you have 4 lists (2^2), you divide again, you have 8 lists (2^3)and so on until your list size is 1

That gives you the equation :

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(you take the lg of each side, lg being the log base 2)

Answer 6

The best way I've always had to mentally visualize an algorithm that runs in O(log n) is as follows:

If you increase the problem size by a multiplicative amount (i.e. multiply its size by 10), the work is only increased by an additive amount.

Applying this to your binary tree question so you have a good application: if you double the number of nodes in a binary tree, the height only increases by 1 (an additive amount). If you double it again, it still only increased by 1. (Obviously I'm assuming it stays balanced and such). That way, instead of doubling your work when the problem size is multiplied, you're only doing very slightly more work. That's why O(log n) algorithms are awesome.