Big O - O(log(n)) code example

Question

Like the Big O notation "O(1)" can describe following code:

O(1):

    for (int i = 0; i < 10; i++) {
        // do stuff 
        a[i] = INT;
    }

O(n):

    for (int i = 0; i < n; i++) {
        // do stuff 
        a[i] = INT;
    }

O(n^2):
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // do stuff
            a[i][j] = INT;
        }
    }

• What code can O(log(n)) describe?

Another question:

• What solutions are there for "Big O problems" (what to do, when getting a lot of data as an input)?

Solution 1

Classic example:

while (x > 0) {  
   x /= 2;  
}  

This will be:

Iteration |   x
----------+-------
    0     |   x
    1     |  x/2
    2     |  x/4
   ...    |  ...
   ...    |  ...
    k     |  x/2^k 

2^k = x → Applying log to both sides → k = log(x)

Solution 2

Simplest code with a for loop that you would use to represent:

O(1):

function O_1(i) {
    // console.log(i);
    return 1
}

O(n):

function O_N(n) {
    count = 0;
    for (i = 0; i < n; i++) {
        // console.log(i);
        count++;
    }
    return count
}

O(n²):

function O_N2(n) {
    count = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            // console.log(i, j);
            count++;
        }
    }
    return count
}

O(Log₂(n)):

function O_LOG_2(n) {
    count = 0;
    for (var i = 1; i < n; i = i * 2) {

        count++;
    }
    return count
}

O(Sqrt(n)):

function O_SQRT(n) {
    count = 0;
    for (var i = 1; i * i < n; i++) {
        // console.log(i);
        count++;
    }
    return count
}

Solution 3

From definition, log(n) (I mean here log with base 2, but the base really doesn't matter), is the number of times, that you have to multiply 2 by itself to get n. So, O(log(n)) code example is:

i = 1
while(i < n)
    i = i * 2
    // maybe doing addition O(1) code

In real code examples, you can meet O(log(n)) in binary search, balanced binary search trees, many resursive algoritmhs, priority queues.

Solution 4

For O(logn), please have a look at any code that involves divide and conquer strategy Example: Merge sort & quick sort(expected running time is O(nlogn) in these cases)

Solution 5

Binary Search is an example O(log(n)). http://en.wikipedia.org/wiki/Binary_search_algorithm.

View more solutions