Error Geek: Big O calculation rules

There are rules which helps us to identify Big O notations.

Rule 1 :- Worst case

Rule 2 :- Remove Constants

Rule 3 :- Different terms for input

Rule 4 :- Drop Non dominants

Rule 1:

The very first role when it comes to big-O that is worst case when calculating big.

if you look at above function we're looping through the entire array to find "rakesh".

package com.algo.practise;

import java.util.concurrent.TimeUnit;

public class Performance {
 public static void main(String[] args) {
  String ar[] = { "rks", "rk", "rakesh", "singhania", "kumar" };
  long timeMilli1 = System.nanoTime();

  for (int i = 0; i < ar.length; i++) {
   System.out.println("Loop");
   if (ar[i].equals("rakesh")) {
    System.out.println("found");    
   }
  }

  long timeMilli2 = System.nanoTime();
  long durationInMs = TimeUnit.MICROSECONDS.convert(timeMilli2 - timeMilli1, TimeUnit.NANOSECONDS);
  System.out.print(durationInMs + " MICROSECONDS");
 }
}

output:

Loop
Loop
Loop
found
Loop
Loop
217 MICROSECONDS

Well "rakesh" was only the third member in this array. And when we run this function we found "rakesh".

But the funny thing is this function ran 5 times not 3 times. We already found "rakesh" then why to run 5 times.

We can make this function a little bit more efficient . If a condition is met we just break out of this loop.

Rule 2 :

The second role when it comes to big-O that is remove constants when calculating big.

package com.algo.practise;

import java.util.concurrent.TimeUnit;

public class Performance {
 public static void main(String[] args) {
  String ar[] = { "rks", "rk", "rakesh", "singhania", "kumar" };
  long timeMilli1 = System.nanoTime();

  for (int i = 0; i < ar.length; i++) {
   System.out.println("Loop");
   if (ar[i].equals("rakesh")) {
    System.out.println("found");
    return;
   }
  }

  long timeMilli2 = System.nanoTime();
  long durationInMs = TimeUnit.MICROSECONDS.convert(timeMilli2 - timeMilli1, TimeUnit.NANOSECONDS);
  System.out.print(durationInMs + " MICROSECONDS");
 }
}

Preview:

Loop
Loop
Loop
found

Well when it comes to big O.

Big-O only cares about the worst case ,Well the worst case is that "rakesh" is at the very end.

So even if we have this break statement we're still going to run as 10 times because "rakesh" is at the end.

package com.algo.practise;

import java.util.Arrays;
import java.util.concurrent.TimeUnit;

public class Performance {
 public static void main(String[] args) {
  String ar[] = { "rks", "rk", "rakesh", "singhania", "kumar" };
   String[] large=new String[1000];
  Arrays.fill(large, "rakesh");

  // Returns current time in millis
  long timeMilli1 = System.nanoTime();
  for (int i = 0; i < ar.length; i++) {
   if (ar[i].equals("rakesh")) {
    System.out.println("found");
   }
  }
    
  for (int i = 0; i < ar.length; i++) {
   if (ar[i].equals("rk")) {
    System.out.println("found");
   }
  }

                for (int i = 0; i < 100; i++) {
          System.out.println("found");
  }

}
}

here Big O is O(2n+100)

so we can ignore constants like 100 and 2 as an array gets bigger and bigger we don't care about adding an extra 100 because if n is a million adding an extra hundred on there another 100 steps doesn't really matter.

So our Big O results in O(n) after dropping constants .

Rule 3:

That is different terms for inputs ,So let's look at an example.

package com.algo.practise;

import java.util.Arrays;

public class Performance {
 public static void main(String[] args) {
  String ar[] = { "rks", "rk", "rakesh", "singhania", "kumar" };
   String[] large=new String[1000];
  Arrays.fill(large, "rakesh");
  
  
  for (int i = 0; i < ar.length; i++) {
   if (ar[i].equals("rakesh")) {
    System.out.println("found");
   }
  }
  
  
  for (int i = 0; i < large.length; i++) {
   if (large[i].equals("rakesh")) {
    System.out.println("found");
   }
  }
  
 }
}

I have the exact same function we saw in Rule 2

We have the array and we just have two loops here.

And as I said before we dropped the constants it becomes all of an O(n) in Rule 2.

but the third rule states that different terms for inputs and what that means is . The first one and then the second one are two different inputs.

One could be a hundred items long.

Another one can be just one item.

So Big O become O(a+b) where a and b are arbitrary letters.

If we have nested loops then Big O will get changed

class Main {
    public static void main(String[] args) {
        System.out.println("Hello World!");
        int[] numbers = {1,2,3,4,5};
        for(int j=0;j<numbers.length;j++){
            for(int i=0;i<numbers.length;i++){
                System.out.println(numbers[i]+","+numbers[j]);
            }
        }
    }
}

it becomes O(a*b).

Rule 4:

drop non dominance or drop non-dominant terms.

Look at below examples

package com.algo.practise;

public class Performance {
 public static void main(String[] args) {
  int ar[] = { 1,2,3,4,5,6};
  
  
  for (int i = 0; i < ar.length; i++) {
   System.out.println(ar[i]);
  } // O(n)
  
  System.out.println("Sum of number");
  for (int i = 0; i < ar.length; i++) {
   for (int j = 0; j < ar.length; j++) {
    System.out.println(ar[i]+ar[j]);
   }
  }
  //O(n^2)
 }
}

So again just looping over and logging out the numbers and then we have another step in here we're summing the pair .

That is where adding each number one after another.

So if we find out the Big O of this method it comes out to be

O(n) + O(n^2)

By Rule number four we want to drop the non dominant terms.

That means we care about the most important term in this case.

We actually drop the n and just have n^2 .

which results in O(n^2).

Error Geek

Thursday 5 September 2019

Big O calculation rules

No comments:

Post a Comment

Spring boot with CORS

Followers