algorithm Big-O Notation O(log n) types of Algorithms

Help us to keep this website almost Ad Free! It takes only 10 seconds of your time:
> Step 1: Go view our video on YouTube: EF Core Bulk Extensions
> Step 2: And Like the video. BONUS: You can also share it!

Example

Let's say we have a problem of size n. Now for each step of our algorithm(which we need write), our original problem becomes half of its previous size(n/2).

So at each step, our problem becomes half.

StepProblem
1n/2
2n/4
3n/8
4n/16

When the problem space is reduced(i.e solved completely), it cannot be reduced any further(n becomes equal to 1) after exiting check condition.

  1. Let's say at kth step or number of operations:

    problem-size = 1

  2. But we know at kth step, our problem-size should be:

    problem-size = n/2k

  3. From 1 and 2:

    n/2k = 1 or

    n = 2k

  4. Take log on both sides

    loge n = k loge2

    or

    k = loge n / loge 2

  5. Using formula logx m / logx n = logn m

    k = log2 n

    or simply k = log n

Now we know that our algorithm can run maximum up to log n, hence time complexity comes as
O( log n)


A very simple example in code to support above text is :

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

So now if some one asks you if n is 256 how many steps that loop( or any other algorithm that cuts down it's problem size into half) will run you can very easily calculate.

k = log2 256

k = log2 2 8 ( => logaa = 1)

k = 8

Another very good example for similar case is Binary Search Algorithm.

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}


Got any algorithm Question?