Skip to main content

Big O calculation rules

Image
By

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".

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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:
1
2
3
4
5
6
7
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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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:
1
2
3
4
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.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

33
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.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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).





Comments

Post a Comment

Popular posts from this blog

Extent report plugin for cucumber framework

By
Extent Reports  are the most popular  reporting  used with Selenium. ExtentReport API makes our life easy to generate interactive  report  with simple configuartions. It supports almost all Java and .NET test frameworks such as TestNG , JUnit , NUnit etc Here we are discussing about  a plugin which is build on  Extent Report specially for Cucumber. This plugin is used to simple out the implementation of  Extent Report  in  Cucumber Framework .  We are creating a maven project to implement the integration of our plugin with cucumber 1. Create new maven project in any tool eclipse/sts/intellij 2. Open pom.xml and update below entries. Step 1 : Add Cucumber Extent Reporter library to Maven Project Add  cucumber-extentsreport <dependency>      <groupId> com.vimalselvam </groupId>      <artifactId> cucumber-extentsreport </artif...
153 comments
Read more

java: You aren't using a compiler supported by lombok, so lombok will not work and has been disabled.

By
  In order to make projects compile with the existing builds of Lombok processor, as a workaround you can use the flag -Djps.track.ap.dependencies=false which should be added to File | Settings | Build, Execution, Deployment | Compiler | Build process VM options field. This will disable collection of dependencies specified by an annotation processor when Filer methods are called
Post a Comment
Read more

Execution default of goal org.springframework.boot:spring-boot-maven-plugin:1.2.3.RELEASE:repackage failed: Unable to find main class

By
Solutions:  Solution 1 : You needed to change the packaging parameter to jar from pom. Also, the repositories , pluginRepositories , the maven-compiler-plugin and the spring-boot-maven-plugin's version and executions weren't needed. Solution 2:  Try mvn install and see if it works Solution 3: Preview: <properties> <!-- The main class to start by executing java -jar --> <start-class> com.mycorp.starter.HelloWorldApplication </start-class> </properties> Solution 4: Enable the main() method in your Application.java. Configure spring-boot-maven-plugin to specify the class with the main class (Spring should find it anyway if you have one, but good to be explicit): Preview: <plugin> <groupId> org.springframework.boot </groupId> <artifactId> spring-boot-maven-plugin </artifactId> <version> ${spring-boot-version} </version>...
Post a Comment
Read more