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

Classic example:

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

This will be:

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

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


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.


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)