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