Appendix: Big O

I feel like this is one of the most common questions that come up in interviews, and so few people understand how it is implemented, even if they have heard of it. Big O is something that can really help you to be a better engineer, simply by understanding it, and coding with its lessons.

First of all, to move forward, it is important that you understand what Big O is. I will summarize below, but I want to link you to a GREAT video talking about Big O and some other common data structures.

Programming with Mosh | Data Structures and Algorithms for Beginners

I have found Mosh to be a great teacher, and he does a good job at covering the building blocks that are often overlooked.

This question comes up in interviews often when you have written something, and the interviewer is interested to know if you understand the implications of your code.

Let me first give you a brief explanation of Big O, in case you don’t have time to watch the video.

The overall goal in utilizing Big O in your code is to determine the WORST CASE SCENARIO of how much:
A: CPU TIME. – Referred to as Time
B: RAM – Referred to as Weight
your code will require.

If you have a function that does a single thing, and is static, even if you have parameters passed, it is a CONSTANT function and has a Big O of 1. Noted as O(1).

function runMe(nums: number[]) {
  console.log(nums[0]);
}

It does not matter if you have 1 or 1,000 commands in that function. If it will only ever be run once when runMe is called, it is a CONSTANT function with a Big O of 1.

If you take the same code, and add a loop (that iterated through the array passed), then it becomes a LINEAR function. A single loop means that the length of the array passed, which is dynamic, dictates the amount of resources allocated for the call of that function.

function runMe(nums: number[]) {
  for ( let i = 0; i < nums.length; i++ ) {
    console.log(nums[i]);
  }
}

This means that your code will be running a Big O of “n”. Noted as O(n).

This keeps going, but I want to describe how this goes from here, Let’s take the same function again, and add a second loop. If we nest loops, our O(n) will become O(n^2) or Big O of n squared. This quickly starts to identify the power of understanding Big O.

function runMe(nums: number[]) {
  for ( let i = 0; i < nums.length; i++ ) {
    for ( let j = 0; j < nums.length; j++ ) {
      console.log(`${nums[i]} ${nums[j]`);
    }
  }
}

This function shows a QUADRATIC function.

So how do we speak about this? How does it help us?

If you write the last function, and the interviewer asks you to describe the Big O in Time. You could say that this is a Big O of n^2. This is because that the length of the array not only is iterated through, but for each iteration, there is a full loop of that numbers iteration as well. So instead of creating a line of text from beginning to end, it would create a line of text from beginning to end, for each element in the array. Sometimes words are not good for explaining this. Big O of n^2 with an array that has a length of 5, is like creating a data table like this:

1	2	3	4	5
1	2	3	4	5
1	2	3	4	5
1	2	3	4	5
1	2	3	4	5

By looking at the table, it is easy to see that your array with a length of 5, creates a table that has 25 cells in it. Which adds clarity around why the Big O is O(n^2), because 5^2 = 25.

Ideally, you only want to have a Big O with any power of N, if you cannot think of any other way to accomplish this goal. You want O(n^i) to be as small as possible. As it requires fewer CPU Cycles.

So, how does this affect RAM? How can we tell what the Big O for the weight? I will modify our function a bit to make it clearer. When thinking about TIME we want to go through the code in our head, and determine how many times a command will be run as a worst case scenario. When thinking about WEIGHT we want to consider how much memory we are occupying within the function.

function runMe(nums: number[]) {
  let numberMatrix: number[][] = [];
  for ( let i = 0; i < nums.length; i++ ) {
    numberMatrix[i] = []
    for ( let j = 0; j < nums.length; j++ ) {
      numberMatrix[i][j] = `${nums[i]} ${nums[j]`;
      console.log(`${numberMatrix[i][j]`);
    }
  }
}

For this function, we are still doing the double loop. But for each iteration, we are adding to how much information we are storing in memory. So, if the length of nums is n, then the Big O for Weight is O(n^2) because the length of the array being passed in is creating arrays/objects within memory that are literally n^2.

As this question comes up frequently, read this document until you understand it. Watch the video I posted above. And when you write a function, think about what the Big O of that function is. Then think about if there is anything you could do to decrease its Big O.

I have found that this method helps me start to separate concerns within a function, make my code more modular, write more pure functions, write my code to be more testable, and best of all, make the code take as little time and space as possible.