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

What's log_b(n)?

It is the number of times you can cut a log of length n repeatedly into b equal parts before reaching a section of size 1.

Answer 2

The complete binary example is O(ln n) because the search looks like this:

1 2 3 4 5 6 7 8 9 10 11 12

Searching for 4 yields 3 hits: 6, 3 then 4. And log2 12 = 3, which is a good apporximate to how many hits where needed.

Answer 3

If you are looking for a intuition based answer I would like to put up two interpretations for you.

1. Imagine a very high hill with a very broad base as well. To reach the top of the hill there are two ways: one is a dedicated pathway going spirally around the hill reaching at the top, the other: small terrace like carvings cut out to provide a staircase. Now if the first way is reaching in linear time O(n), the second one is O(log n).

2. Imagine an algorithm, which accepts an integer, n as input and completes in time proportional to n then it is O(n) or theta(n) but if it runs in time proportion to the number of digits or the number of bits in the binary representation on number then the algorithm runs in O(log n) or theta(log n) time.

Answer 4

These 2 cases will take O(log n) time

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

Answer 5

Overview

Others have given good diagram examples, such as the tree diagrams. I did not see any simple code examples. So in addition to my explanation, I'll provide some algorithms with simple print statements to illustrate the complexity of different algorithm categories.

First, you'll want to have a general idea of Logarithm, which you can get from https://en.wikipedia.org/wiki/Logarithm . Natural science use e and the natural log. Engineering disciples will use log_10 (log base 10) and computer scientists will use log_2 (log base 2) a lot, since computers are binary based. Sometimes you'll see abbreviations of natural log as ln(), engineers normally leave the _10 off and just use log() and log_2 is abbreviated as lg(). All of the types of logarithms grow in a similar fashion, that is why they share the same category of log(n).

When you look at the code examples below, I recommend looking at O(1), then O(n), then O(n^2). After you are good with those, then look at the others. I've included clean examples as well as variations to demonstrate how subtle changes can still result in the same categorization.

You can think of O(1), O(n), O(logn), etc as classes or categories of growth. Some categories will take more time to do than others. These categories help give us a way of ordering the algorithm performance. Some grown faster as the input n grows. The following table demonstrates said growth numerically. In the table below think of log(n) as the ceiling of log_2.

Simple Code Examples Of Various Big O Categories:

O(1) - Constant Time Examples:

• Algorithm 1:

Algorithm 1 prints hello once and it doesn't depend on n, so it will always run in constant time, so it is O(1).

print "hello";

• Algorithm 2:

Algorithm 2 prints hello 3 times, however it does not depend on an input size. Even as n grows, this algorithm will always only print hello 3 times. That being said 3, is a constant, so this algorithm is also O(1).

print "hello";
print "hello";
print "hello";

O(log(n)) - Logarithmic Examples:

• Algorithm 3 - This acts like "log_2"

Algorithm 3 demonstrates an algorithm that runs in log_2(n). Notice the post operation of the for loop multiples the current value of i by 2, so i goes from 1 to 2 to 4 to 8 to 16 to 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• Algorithm 4 - This acts like "log_3"

Algorithm 4 demonstrates log_3. Notice i goes from 1 to 3 to 9 to 27...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• Algorithm 5 - This acts like "log_1.02"

Algorithm 5 is important, as it helps show that as long as the number is greater than 1 and the result is repeatedly multiplied against itself, that you are looking at a logarithmic algorithm.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O(n) - Linear Time Examples:

• Algorithm 6

This algorithm is simple, which prints hello n times.

for(int i = 0; i < n; i++)
  print "hello";

• Algorithm 7

This algorithm shows a variation, where it will print hello n/2 times. n/2 = 1/2 * n. We ignore the 1/2 constant and see that this algorithm is O(n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O(n*log(n)) - nlog(n) Examples:

• Algorithm 8

Think of this as a combination of O(log(n)) and O(n). The nesting of the for loops help us obtain the O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

• Algorithm 9

Algorithm 9 is like algorithm 8, but each of the loops has allowed variations, which still result in the final result being O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O(n^2) - n squared Examples:

• Algorithm 10

O(n^2) is obtained easily by nesting standard for loops.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

• Algorithm 11

Like algorithm 10, but with some variations.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O(n^3) - n cubed Examples:

• Algorithm 12

This is like algorithm 10, but with 3 loops instead of 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";

• Algorithm 13

Like algorithm 12, but with some variations that still yield O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Summary

The above give several straight forward examples, and variations to help demonstrate what subtle changes can be introduced that really don't change the analysis. Hopefully it gives you enough insight.

Answer 6

But what exactly is O(log n)

What it means precisely is "as n tends towards infinity, the time tends towards a*log(n) where a is a constant scaling factor".

Or actually, it doesn't quite mean that; more likely it means something like "time divided by a*log(n) tends towards 1".

"Tends towards" has the usual mathematical meaning from 'analysis': for example, that "if you pick any arbitrarily small non-zero constant k, then I can find a corresponding value X such that ((time/(a*log(n))) - 1) is less than k for all values of n greater than X."

---

In lay terms, it means that the equation for time may have some other components: e.g. it may have some constant startup time; but these other components pale towards insignificance for large values of n, and the a*log(n) is the dominating term for large n.

Note that if the equation were, for example ...

time(n) = a + blog(n) + cn + dnn

... then this would be O(n squared) because, no matter what the values of the constants a, b, c, and non-zero d, the d*n*n term would always dominate over the others for any sufficiently large value of n.

That's what bit O notation means: it means "what is the order of dominant term for any sufficiently large n".