Whether you’re learning to code, looking for a coding job, or trying to make a specific coding task more efficient, Big O Notation is something you’re either already thinking about, or should be thinking about.
Simply put, Big O Notation is the comparison of how efficiently one solution to an algorithm runs compared to others. It’s the mathematical way of recognizing how demanding a solution is as the inputs grow to be very, VERY large.
Big O Notation applies to both time and space; think about how much time an algorithm will take to run as the inputs get very large, and similarly how much space does that solution demand.
Let’s take a look at what the Big O Chart for Time Complexity looks like:
As we can see here, on the X axis is the size of input data, and on the Y axis is the time to complete. The labels on the right and top show what the Big O Notation is for each trend, with some simple color guidance as to what’s the most efficient (green), and what’s the least efficient (red).
N, you might ask?
N is the number of inputs, and remember, the main point of Big O Notation is to recognize how scalable our solution is, so in theory we are thinking about N, the number of inputs, to be a huge number, approaching infinity.
Let’s take a look at some of the more common Big O’s, and what they mean. (These examples use seconds as a unit, although it is unlikely it would ever be exactly that, which is used strictly to simplify the concept.)
In order from MOST efficient to LEAST efficient:
O(1)- “O of One”- means CONSTANT time. No matter how many inputs are provided, the solution is still run in the same amount of time. One input? One million inputs? It Doesn’t matter!
O(log N)- “O of log N”- is a tricky one. Think of log (logarithms) as reverse exponentials. As you exponentially increase the number of inputs, the time it takes increases exponentially less. This is typically the most efficient solution possible for some of the more basic algorithm problems, including binary search. For example, if 1 input took 1 second, 10 inputs would take 2 seconds, 100 inputs = 3 seconds, 1,000 inputs = 4 seconds, etc.
O(N)- “O of N”- means linear complexity. The time a solution takes is linear to the number of inputs. This is typical of looping, and for JS array methods. For example, if 1 input took 1 second, 10 inputs would take 10 seconds, 100 inputs = 100 seconds, etc.
O(N²)- “O of N squared”- means quadratic complexity. The time a solution takes grows exponentially as the number of inputs increases. This is commonly a byproduct of nested looping, or nested JS array methods. Whenever possible, it’s typically best to avoid nesting loops, and instead use another form of data mutation, like objects for instance. For example, if 1 input took 1 second, 10 inputs would take 100 seconds, 100 inputs would take 10,000 seconds. Imagine 1 million inputs…. uh oh!
- In general there are many different ways to solve any algorithm, and Big O Notation is how we compare which solutions are the most scalable, that is which are most efficient as the input size becomes VERY large.
- Some solutions are great when an input is small, but will quickly crash or freeze your computer as the input grows, or simply take MUCH longer to complete.
- Whenever possible, it’s best to avoid nested loops or nested array methods. It always depends on what the data is and what the method is doing, but there’s a lot of surprising side effects of using JS array methods when it comes to time complexity.
Thanks for reading, I’ll be back with more on Big O Notation soon!