What is Big ‘O’ Notation? Why should you care?
If you are just beginning your journey into the magical world of code, chances are you have never heard of the term “Big O Notation”. Maybe you have heard of it but thought you needed a computer science degree to understand it. Well, I’m here to show you that it’s not that scary after all!
I’m not scared! C’mon tell me what it is!
Well alright then, since you are so pushy I’ll assume you already know a programming language. For this post, I will use JavaScript.
Big O Notation is simply used to measure how well a programming algorithm scales as the amount of data involved increases. Big O Notation is represented in this format: O(1)
Where the ‘O’ symbolizes that we are talking about Big O Notation and the ‘1’ represents the scaling factor of the algorithm. I know that seems vague for now but just stick with me it should clear up as you see some examples.
Let’s start with the same example I gave above. O(1).
Say I need a function that adds 10 to any number given as an argument.
This function has an O factor of O(1) because no matter how large the input becomes the program will run in the same amount of time. Simple right?
Do you want more? Well alright champ, since you are so smart O(n²) is next!
Now say I have an array of Google stock prices (googleStocksToday) where the index of each element is the hours past 9:00AM and the last element represents 4:00PM.
I need a function that will return the highest profit possible during that day of trading.
This function has an O factor of O(n²). This means that this algorithm has to take n² steps to completely run (where n is equal to the size of googleStocksToday). If you look back at the code, it’s not too hard to see where we get the n². Each time the outer loop runs the inner group iterates through the entire array. In this case, since the stock market is open for eight hours so our O factor works out to be 8² = 64. Hm, sixty-four steps seem manageable for today’s computers but, what if we wanted to keep track of Google prices every minute? Let’s do the math. Our new array will have 480 elements, so our new O factor will be 480² = 230,400. Yuck! Generally, if your goal is to write efficient code, you want to avoid O(n²) when possible.
Do you think we can improve the O factor?
Of course, we can!
The next best O factor we can aim for is O(n). Hm, is there some way we can solve this with just one iteration of the array? Let’s give it a try!
Can you see why this algorithm has a factor of O(n)? Yes, that is right! This function only has to loop the array once to find our answer. If we look back at our previous test, we can see how many steps we are saving.
Array in hours:
O(n²) = 64 vs O(n) = 8
Array in minutes:
O(n²) = 230,400 vs O(n) = 430
Jolly optimization!
There are others I haven’t covered (O(log n) and O(2^n)) but I don’t want to ramble and I’m sure your curiosity will lead you to the answer. If you like the way I break it down, let me know in the comments and I will be happy to make another post!
Why should I care? I got the solution anyway!
Good question! While you did get a solution, it does not mean it is always the most efficient one. With mobile devices sweeping the market, writing efficient code is becoming the industry standard. You also become a much more attractive developer if you write efficient code since you can save your company the cost of maintaining more servers than they have to. So why not start now?! Look back at your own code and see if you can determine the O factor! Then take it to the next level and improve!
initcommit 