Blog / Data Structures & Algorithms
Big O Rules
  • Nov 22, 2020
  • 86
  • 56

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.


Advertisement
 


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, n2 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, n2 is always return the biggest value compare to n and 1. So, we can simplify this to O(n2) as time complexity for this function.

Read more in this series:


If you have a Website or a Web API developed by using .Net Core and looking for a way to publish your applications, this post will explain how to do it using GoDaddy Windows Hosting.Note: at this mome ...

Search text in Stored Procedure in SQL SELECT DISTINCT o.name AS Object_Name, o.type_desc FROM sys.sql_modules m INNER JOIN sys.objects o ON m.object_id = o ...

Using cherry-pick to select specific commits for your Pull Request.1. Create a new branch based on the target of the Pull Requestgit branch cherry-branch origin/master2. Switch to a new branchgit chec ...

After deployment Angular and API on IIS, it's working fine unless I refresh the page. Once refreshed, the web encountered 404 error. In this article, I will explain how to resolve this.Since Angular i ...

There are some benefits of keeping both UI and API parts in the same place for small projects. In this article, I will explain how I did to deploy Angular Web and ASP .Net Core API in the same folder ...

I got CORS error after publishing my API and Angular app to IIS even though CORS is enabled and the origins of the Angular app is added. Below is how I resolved this issue.Just simple, make sure you s ...

In Object-Oriented Programming, S.O.L.I.D refers to the first five design principle for the purpose of making software designs more understandable, flexible, and maintainable. The principles was first ...

1. The Situation:Error Message:&nbsp;Pulse Secure Application failed to load Java. Please install correct JRE version.Description: This issue happens when I'm using a M1 Mac with a correct version of ...

Accelerated Mobile Pages (AMP)&nbsp;focuses on delivering static content from publishers as quickly as possible and possibly rewards early adopters with a boost in rank. Let's see how to implement it ...