What is Big O Notation?

What is Big O Notation?

Lots of developers say if you are a senior, you should know what Big O Notation is, articulate it and also apply this when you actually write algorithms.

Frankly, this is something we really need to grind away at if you are not from a computer science background and this is what we need to learn to think like a developer.

If you are an aspiring developer who wants to understand what Big O Notation is, I am with you and let me explain it to you. The best way to learn something new is when you try to teach it to someone as well.

Literally, Big O Notation is a jargony way to describe how developers talk about the time and space complexity during the runtime of an algorithm. Even the term 'Algorithm' is just a set of rules which is written by engineers to tell computers how to solve a problem. If you still couldn't comprehend what I am talking about, don't worry. This is not simple algebra like 1 + 1 = 2.

As I mentioned, time and space affect the efficiency of the codes as the inputs grow. For example, we have an array with unordered 100 values and we need to find the total number of unique numbers from the array. As we do not know what numbers are in the array, of course, this is where the time and space complexity would affect the code quality depending on how we write the codes.


O(N2) quadrantic way carbon (1).png

We create a new array to store the unique value of the original array. While looping through the original array, we also need to loop through the new array under the hood to find whether a current value from the original array is unique or not. A nested loop or quadrantic search is not an efficient way to solve the problem with Arrays as the input grows, it will go slower exponentially.


O(N) linear way carbon.png

We will loop through the entire array to find the total number of unique numbers in the array. However, one time only! While looping through the entire original array, we are creating a new key of an empty object which was assigned at the beginning of the code block. That is, the object doesn't have the key with the same value of the array. The object will have the new key and it keeps going on until it reaches the end of the array. This is called a frequency counter pattern. In summary, when you find a specific value from an object, this search is obviously Constant O(1) search. If you have to find the value from an array, it would be a linear search.


So far, we have talked about a fraction of Time complexity of Big O Notation. Then, what about Space complexity? The Space refers to the memory which is allocated to a computer in order to run the code block. If you are a JavaScript developer, you must have heard of a call stack. That's what it is. The reference types, such as variables generally take up O(N) spaces where N is the length of the array or the number of keys of an object.

In a nutshell, Big O Notation is the way to analyse the performance of an algorithm in terms of time and space complexity. I hope this explanation gives you a better understanding of the big mystery of Big O Notation.