Hello!
Today we will be learning about Big O Notation. If you’ve been writing code professionally, then you must’ve heard of Big O’ (as it is popularly known) even if it was in passing.
So what is Big O’?
Big O Notation
Big O is a measure of work. It is a means of calculating the space (how much storage you are using) and time of a program or algorithm. Below is a chart showing Big O complexity in increasing order. For a more detailed technical explanation of Big O, please see this post by @_alternatewolf.
What does this mean to a five year old?
As I previously mentioned, Big O helps us measure how much time and space (storage) we expend while trying to accomplish a task.
First we will tackle space.
We are out on the farm to pick apples. However, we do not have that much money so we can only pick one apple from the farm. How do we decide what apple to pick?
You can pick the best apples you come across and store them in a basket, as in the picture below. When you are done walking the farm, you go through the “best” options in the basket, and pick the best one out of it. However, if you think about this, you are searching for the best apple to pick twice (from the field, and from the basket). You are also actively carrying the basket with you from the beginning till the end. If your arms don’t hurt from carrying this basket at the end, you should be in the olympics. Don’t ask me for what sport.
A second possible approach is that you pick only one apple at any time. The first apple you see is the best apple so far. Keep that apple in hand, and only switch it out with a much more good looking, juicy apple. When you are done with the field, you do not have to search through a basket for the best apple, you would already have it in hand.
Between these two approaches, we see that one uses extra space (by keeping a basket of all good apples) and the other does not. Big O gives us a means to calculate how much space our algorithm uses.
Let’s take a look at time.
Yay! More apples!!!
Today seems like an apple kind of day. I hope you like apples as much as I do.
If I said give me one apple from these baskets, you would not need to think about it. No need to search for it. Just go in, grab the first apple you see, and hand it over to me. This is constant time, O(1). Why? Because no time was spent searching or looking. What if I said get me the one that’s almost spoilt? No, I am not going to eat it. You are going to need to look through all the apples at least once to find the worst one. Given that you touch every apple at least once, you have a Big O of O(n). Known as linear time.
If the apples were arranged (sorted) in some order, you could’ve done it faster by using the two pointer algorithms we discussed last week. That would’ve reduced our time to a possible Big O of O(logn)
Here’s a hint that has always worked for me to decide the Big O of an algorithm.
If I only need to see one item in the input, that is O(1) - Constant
If I have to visit every element in the input, that is O(n) - Linear
If I reduce the input size by half every time, that is O(logn) - Logarithmic
If I have to visit every element in the input more than once, that is O(n^2) - Quadratic
Resources
https://www.linkedin.com/pulse/big-o-notation-simple-explanation-examples-pamela-lovett/
https://betterprogramming.pub/complexity-how-much-time-and-space-does-your-algorithm-take-82598873541f
https://static.packt-cdn.com/downloads/4874OS_Appendix_Big_O_Cheat_Sheet.pdf
Conclusion
Thank you for reading! Glad that we have done this for one month now. See you next week; don’t forget to subscribe if you’ve not subscribed. Subscribers only post will start from next week.