We have been talking about and have a better understanding of what is Big O Notation and different time complexities. In this post, we will learn more about how to calculate Big O, how to simplify it, and the 4 Big O Rules.

1. How to Calculate Big O?

You may not be asked about how to do Big O calculation step by step while doing your interview. Instead, the interviewers may just ask what is the time/space complexity of your algorithm. So, it's better to know a basic idea of how to calculate Big O to come up with a quick answer in your interview.

We will go with an example to know how we can determine the Big O for time complexity of an algorithm. Please consider my comments in below code to see the calculation step by step.

function Func1(inputArray) {
   let a = 1; //This will take O(1) because this step will run only once when execute the function.
   a = 1 + 12; //This will take O(1) because this step will run only once when execute the function.
 
   for (let i = 0; i < inputArray.length; i++) { //This will take O(n) because this step will run n times where n is the size of inputArray.
      let b = i; //This will take O(n) because this step will run n times where n is the size of inputArray.
      a += b; //This will take O(n) because this step will run n times where n is the size of inputArray.
   }
 
   return a; //This will take O(1) because this step will run only once when execute the function.
}
 
Func1([1,2,3,4,5]); 
//Based on the calculation in each step above, we can say this function costs: 
//O(1 + 1 + n + n + n + 1) = O(3n + 3)

2. Simplifying Big O

In the previous example we just did, it was kind of annoying where we had to add things up then have a not so nice Big O Notation: O(3n + 3). Why it is O(3n + 3)? It doesn't look like any of the common time complexities (well, similar to one of them) that we mentioned before! Well, that is just for you to understand how Big O is calculated! Most of the time, when you go into interviews, there is the set of rules, we call it Big O Rules, that you are going to follow where you don't need to do step by step like above. Instead, you just need to look into your function and say what type of Big O it is.

And by following the Big O Rules, we can simplify the above Big O we calculated to below:

O(3n + 3) = O(n) //Linear Time Complexity.

So, let's dive in these Big O Rules to find out what these rules are about!

3. Big O Rule 1: Worst Case

When calculating Big O, we always think about the worst case.

So, what does it mean by thinking about the worst case. Let's look at the function below:

const pokemon = ['Pikachu', 'Meowth', 'Bulbasaur'];
const morePokemon = ['Meowth', 'Bulbasaur', 'Charmander', 'Pikachu'];

  
function catchPikachu (array) {
  
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'Pikachu') {
       console.log('Catch Pikachu!');
       break;
    }
  }
  
}
  
catchPikachu(pokemon);
catchPikachu(morePokemon);

In the example above, the first array has Pikachu as the first element. So, the function just need to loop into the array once since Pikachu has been found the first time. However, the second array has Pikachu as the last element. That means, this function needs to loop the entire input array to find out Pikachu! This is the worst case that the Big O Rule 1 mentions.

No matter how the elements are ordered in the input, we always consider the worst scenario to calculate Big O. In this case, the function takes O(n) time complexity.

4. Big O Rule 2: Remove Constants

After calculating Big O, we need to ignore all constants in the final result to get Big O

Remember how we simplify Big O above? That's is when we remove all constants in the final result to get the final answer of what is the Big O for our function.

Consider another example below:

function aRandomFunction(inputArray) {
   console.log("Starting ...");
 
   var middle = Math.floor(items.length/2);
   var index = 0;
 
   while (index < middle) {
      console.log(items[index]);
      index++;
   }
 
   for (let i = 0; i < 100; i++) {
      console.log('ending ....');
   }
}
 
aRandomFunction([1,2,3,4,5,6]);
//The above function cost O(1 + n/2 + 100) = O(n) time complexity.

5. Big O Rule 3: Different Terms for Inputs

We should have different terms to represent different input size in an algorithm

Let's say, if you have a function that take 2 array inputs which have different size. You should have a different terms representing the size of each input. Please consider below function:

function randomFunction(array1, array2) { //let's say array1 has size of a items, array 2 has size of b items
   array1.forEach(function(item) { //This takes O(a)
      console.log(item);
   });
 
   array2.forEach(function(item) { //This takes O(b)
      console.log(item);
   });
}
 
randomFunction([1,2,3,4,5,6],[1,2]);
//This function cost O(a * b) time complexity

Instead of having 1 term for both input as n, which will result in O(n) time complexity, we should have different terms for each input like a and b. So, the final outcome of time complexity for the above function is O(a * b).

6. Big O Rule 4: Drop Non Dominants

We should worry about the most dominant term and drop others

The most dominant term is the mathematical term which is greater in absolute value than any other (as in a set) or than the sum of the others. Let's consider below example:

function anotherRandomFunction(array) {
  console.log(array[0]); // O(1)
 
  array.forEach(function(item) { // O(n)
     console.log(item);
  });
 
  array.forEach(function(item1) { // O(n^2)
     array.forEach(function(item2) {
        console.log(item1 + item2);
     });
  });
}
 
anotherRandomFunction([1,2,3,4,5]);
//O(n^2 + n + 1) = O(n^2)

In the above example, n² is the most dominant term among others because it is the greatest in absolute value in a set. We can apply any number in the function, n² is always return the biggest value compare to n and 1. So, we can simplify this to O(n²) as time complexity for this function.