How to calculate Big O

We calculate the Big O notation in the following steps.

1. Worst case scenario

The first thing to know before calculating the time complexity is we consider the worst-case scenario.

Consider the following code:

const avengers= [“Iron man”, “Black Panther”,”Spiderman”, “Thor”, “Hulk”];
const chooseAvengers = () => {
for (i = 0; i < avengers.length; i++) {
    console.log(“chooseAvengers Running”);
    if(avengers[i] == “Spiderman”) {
        console.log(“Found”);
        break;
        }
    }
}
chooseAvengers();

Output

chooseAvengers Running
chooseAvengers Running
chooseAvengers Running
Found

So, in the above program, the chooseAvnegers() function runs 4 times. After it finds “Spiderman” the code breaks out of the function. So, even though our loop is supposed to run 5 times it only runs 4 times.

Now, let’s consider the following array.

const avengers= [“Spiderman”, “Black Panther”,”Iron man”, “Thor”, “Hulk”];

On this case the loop would run 1 time.

Now, let’s consider the following array.

const avengers= [“Iron man”, “Black Panther”, “Thor”, “Hulk”, “Spiderman”];

In this case, the loop would run 5 times. As the function runs avenger.length times this is known as the worst case.

We would not know in which position the “Spiderman” will be found. So, we will always consider the worst-case scenario while calculating the Big O notation.

2. Drop the constant

Consider the following code:

const avengers = [“Thor”, “Hulk”, “Spiderman”, “Ironman”, “Black Panther”];
const chooseAvengers = () => {
    console.log(avengers[3]);
    const half = Math.floor(avengers.length/2);
    for(i = 0; i <= half; i++) {
        if(avengers[i] == “Spiderman”) {
            console.log(“Avenger Chosen”);
        }
    }
}
chooseAvengers();

Ok, let’s try to roughly calculate the Big O of the chooseAvengers() function.

Let’s calculate it line by line.

console.log(avengers[3]);

Big O = O(1)

const half = Math.floor(avengers.length/2); 

Big O = O(1)

for(i = 0; i <= half; i++) { // O(n/2)
    if(avengers[i] == “Spiderman”) {
        console.log(“Avenger Chosen”);
    }
}

Big O = O(n / 2)

As the number of input increases the number of steps in the loop also increases. So, we can simply say it is O(n), instead of O(n / 2).

Now, let’s see what the Big(O) of the chooseAvengers() function is:

Big(O) = O(1) + O(1) + O(n)
       = O(2) + O(n)
       = O(2 + n)

To calculate the Big(O), we simply drop the constant value 2. So, the Big O of the above function would be O(n).

Let’s take another example:

const avengers = [“Thor”, “Hulk”, “Spiderman”, “Ironman”, “Black Panther”];
const chooseAvengers = () => {
// first loop
    for(i = 0; i < avengers.length; i++) {
        if(avengers[i] == “Spiderman”) {
            console.log(“Avenger Chosen”);
        }
    }
    // second loop
    for(j = 0; j < avengers.length; j++) {
        if(avengers[j] == “Ironman”) {
            console.log(“Avenger Chosen again”);
        }
    }
}
chooseAvengers();

So, let’s calculate the Big(O) of the chooseAvengers() function step by step:

Big(O) of first loop = O(n)

Big(O) of second loop = O(n)

Now, total Big(O) = O(n) + O(n)
                  = O(n + n)
                  = O(2n)

To calculate the Big(O), we simply drop the constant value 2. So, the Big O of the above function is O(n).

3. Different terms for input

Consider the following code:

const avengers = [“Thor”, “Hulk”, “Spiderman”, “Ironman”, “Black Panther”];
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
const chooseAvengers = () => {
    // first loop
    for(i = 0; i < avengers.length; i++) {
        if(avengers[i] == “Spiderman”) {
            console.log(“Avenger Chosen”);
        }
    }
    // second loop
    for(j = 0; j < numbers.length; j++) {
        if(numbers[j] == 15) {
            console.log(“15 found”)
        }
    }
}
chooseAvengers();

We have two arrays — avengers and numbers. The number of elements in both arrays is different.

One has 5 elements and the other has 15 elements.

As both arrays have a different number of elements giving O(n) for both is not accurate.

So, to our first loop:

Big(O) = O(a)

And to our second loop:

Big(O) = O(b)

So, the Big O of the chooseAvengers() function is O(a + b).

4. Drop non-dominant term

Considered the following code

const avengers = ["Thor", "Hulk", "Spiderman", "Ironman", "Black Panther"];
const chooseAvengers = () => {
    
    // first loop
    for(i = 0; i < avengers.length; i++) { 
        
        if(avengers[i] == "Spiderman") {
            console.log("Avenger Chosen");
        }
    }
    
    // second loop
    for(j = 0; j < avengers.length; j++) { 
        
        if(avengers[j] == "Ironman") {
            console.log("Avenger Chosen again");
        }
    }
    
    // third loop
    for( i = 0; i < avengers.length; i++) {
        
        for(j = 0; j < avengers.length; j++) {
            
            console.log(avengers[i], avengers[j]);
        }
    }
}
chooseAvengers();

The Big(O) of the above code

O(n) + O (n) + O(n²)

Now, the most dominant term here is O(n²).

Why?

This is because when the number of input changes, O(n²) is the term that changes significantly.

We must simply drop the non-dominant term.

So, the Big(O) of the above code is O(n²).