Thursday, 5 September 2019

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

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





By - No comments:

Wednesday, 4 September 2019

Big O notation


Big-O Analysis of Algorithms
The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.
Don't get too hung up on this. We want to use this as an example to measure how long it takes for this function to run. We can do this in Java by saying let's say Time0 is going to start this timer before the loop happens.
And then when the loop ends I'm going to have another timer called T-1 

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" };

  // 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");
   }
  }
 
  long timeMilli2 = System.nanoTime();
  long durationInMs = TimeUnit.MICROSECONDS.convert(timeMilli2 - timeMilli1, TimeUnit.NANOSECONDS);
  System.out.print(durationInMs +" MICROSECONDS");
 }
}

Output:
found
136 MICROSECONDS

it's going to give us the results and microseconds
And if I keep running it I see that it takes a little bit longer but only few microseconds only.
And that's because this is really fast right our computers machines are extremely fast in this day.

So instead of just having a single array let's have the array that now has a lot more items 
Let's just call it large and we can create a massive array by just saying fill new array.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 < large.length; i++) {
   if (large[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
found
found
found
found
19035 MICROSECONDS

that took a lot longer.

What if we had a massive array of 10000.
output :
1
2
3
4
5
found
found
found
found
356321 MICROSECONDS

Well we see that as our input grew our function became slower and slower and slower.

But here's the problem here. If you take this code and run it on your computer while your time is going to be different than mine.

You're going to get frustrated because every time you're on this code is going to be different than my number .It might be a lot faster a lot slower.
Therefore if I call my friend across the world let's call them Anurag and I tell him Hey Anurag my code is so amazing I've created this fine function and it runs in three seconds 1.9 seconds with hundred thousand inputs.

And then Anurag says Ha that's really awesome. But you know what. Mine runs a lot faster runs in 1.5 seconds.

So how can we determine who wins. Do I win or does Anurag win.

Who has better code and this is very common in the computing world. 

Big-O notation is the language we use for talking about how long an algorithm takes to run.

We can compare two different algorithms or in this case functions using big-O and say which one is better




That's all it is.

This is what we call algorithmic efficiency big-O allows us to explain this concept.

Remember how in our function we initially had an array of just one which was finding "rakesh".

But then as we increase that array of 100000.

You saw that the number of operations or the number of things we do in the loop increased over and over and different functions have different big-O complexities. 

Just remember when we talk about Big O and scalability of code we simply mean when we grow bigger and bigger with our input.

No matter what we're looping the way that we have this code set up if we have ten items in the array it's going to be ten operations ten loops.

 We see a little bit of pattern here. We can draw a line through it.

 This is linear rate as our number of inputs increase the number of operations increase as well.

 Now we've learned our very first Big-O notation i.e

 O(n ) or Linear time -- > N is just a random letter I could put x ,I could put Y in here if I want is just an arbitrary letter.
So let's talk about the next one.

 Another very common Big-O notation that you're going to see 
what happens if we have a function like this.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package com.algo.practise;

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

public class Performance {
 public static void main(String[] args) {
  String[] large = new String[10000];
  Arrays.fill(large, "rakesh");
  long timeMilli1 = System.nanoTime();

  // O(1)
  System.out.println(large[50]);

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

No matter how many times you are calling the method we're always just grabbing the specific item in the array.

 If we look at this with an example if we had an array of names and we run it through the function that just takes the 50th item in the array.

 Well the number of operations is one no matter how big the array is We're only doing one thing. So it's a constant time. 

 O(1) - constant






By - No comments:
Labels:
Subscribe to: Posts (Atom)

Spring boot with CORS

CORS (Cross-Origin Resource Sharing) errors occur when a web application running in a browser requests a resource from a different domain or...