Mastering the Coding Interview: Big O

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm.

Big O is calculated based on your input. The question you ask yourself is based on my input how will this problem grow.

Let’s first take a look at the Big O complexity chart which outlines how horrible or excellent a solution is based on it’s Big O.

Big Oh Rules

1. Big O is calculated by using the worst case scenario
2. Constants are dropped: O(31n + n/2 + 1000) would be O(n)
3. Different terms for inputs. If you have multiple inputs/arguments your Big O will contain multiple letters to express the efficiency.
4. Drop the non dominant terms. You can determine what is dominate by plugging in the same number and seeing which one will give you the largest number: O(n² + n + 1) = O(2) = (2² + 2 + 1) = (4 + 2 + 1) = n² : dominant

I’m going to describe the Big O of a few javascript functions based on an input of an array of elements and functions below.

const arr = [‘a’ ,’b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘I’];

Big O(1)

function constantGrowth(x) {
return x[0]; //O(1)
}

This function has a Big O(1) because no matter the size of our input this function will retrieve the first element and return that back.

constantGrowth(arr);

Big O(n)

function n-Growth(x) {
const max = x.length;//O(1)
for(let i = 0; i < max; i++){ // O(n)
console.log(x[i]); //O(1)
}

for(let i = 0; i < max; i++){ // O(n)
console.log(x[i]); //O(1)
}
}

n-Growth(arr); // O(1 + n + 1 + n) = O(2n + 2) = O(n)

This function has a Big O(n) because based on the rules the worse case scenario is we have to go through the entire length of the input, the determinant is n, and after dropping the constants from 2n we are left with O(n)

Bonus: Big O(n + m)

function n-Growth(x, y) {
const max = x.length;//O(1)
const max2 = y.length;//O(1)

for(let i = 0; i < max; i++){ // O(n)
console.log(x[i]); //O(1)
}

for(let i = 0; i < max2; i++){ // O(m)
console.log(y[i]); //O(1)
}
}

n-Growth(arr); // O(1 + 1+ n + 1 + m + 1) = O(n + m + 4) = O(n + m)

This function has a Big O(n +m ) because based on the rules the worse case scenario is we have to go through the entire length of the input, using different terms for each input, we are left with O(n + m)

Big O(n²)

function nSquared-Growth(x) {
const max = x.length;//O(1)
for(let i = 0; i < max; i++){ // O(n)
for(let i = 0; i < max; i++){ // O(n)
console.log(x[i]); //O(1)
}
}
}

nSquared-Growth(arr); // O(1 + n * n + 1) = O(n² + 2) = O(n²)

This function has a Big O(n) because based on the rules the worse case scenario for our input we have to go through the entire length of the array for each item in the array, the determinant is n², we are left with O(n²)

Bonus: Big O(n * m)

function nm-Growth(x, y) {
const max = x.length;//O(1)
const max2 = y.length; //O(1)
for(let i = 0; i < max; i++){ // O(n)
for(let i = 0; y< max; i++){ // O(m)
console.log(x[i]); //O(1)
}
}
}

nm-Growth(arr); // O(1 + 1 + n * m + 1) = O(n * m)

This function has a Big O(n) because based on the rules the worse case scenario for our inputs we have to go through the entire length of the y array for each item in the x array, the determinant is n & m, we are left with O(n * m)

You typically won’t have to calculate the Big O line by line and can instead commit this cheat sheet below to memory. Having an understanding of the rules coupled with this cheat sheet will help you quickly and accurately determine Big O

Cheat Sheet