Why worry about Big O?
As someone who has been coding for only a few months, I'll admit the concept of Big O notation was one that I avoided at first because it seemed complicated. When I first started I wasn't trying to figure out the best way to code something I was just trying to figure out code that works. While that's fine when you're first starting out, I soon realized how much faster I could make my code run by refactoring a couple lines or using a different method. And that is essentially why programmers use Big O notation to describe how fast particular code is especially when you start dealing with large data structures. Here I'll go over three main examples O(1), O(n), and O(n²) to give you a basic understanding of what Big O notation is.
So what is Big O?
Essentially, Big O is a measurement of how quickly a certain block of code will run based on the input size(n). What do I mean by input size? Take this function for example...
This function takes in an array and the returns that array. The input size in this case would be the size of the array. So what is Big O? Big O is measuring how fast this function will run if you increase the size of the array that is passed in.
Let's say this is the array we're passing in to our function now. Will the function run slower now? As you may have guessed, the answer is no. In fact this function will have the same run time for pretty much any size of array that we pass in. So how do we get the O notation for this function or any function for that matter? Well the way to visualize this is through the use of graphs.
If you can think back to when you were learning about equations for graphs, you might remember that for a straight line parallel to the x-axis the equation is y = c. C being a constant. If a function never changes in how fast it operates given the input (n), we know that it will be a straight line at whatever the constant(c) is for that specific function. In Big O terms we call that O(1). Although you can replace the 1 with whatever your constant is, typically in coding 1 is used to show that the function doesn't change in time with a growing input.
Now can take a look at an example that is slightly more complicated, O(n).
As you can see in this function we have a basic for loop that returns each element within the given array. The bigger the array is that we give to this function, the longer it will take for the function to run. Here is a graph that depicts how this function works.
So the bigger the size of our input(n) the longer it takes for the function to run. The equation for this graph would be y = ax + b or y = an + b. When we think about O notation, what we're searching for is the worst possible outcome or in other words the fastest growing term in our equation. If we take a look at the equation, we know that the fastest growing term is (an). As we increase the value of n (our input) , our value for y (time) will also increase. Since the coefficient (a) in this equation is dependent on the specific function, we don't have to really worry about it. This leads us to the notation O(n). O(n) basically just means that the function is directly relying on the size of the input(n).
Finally, we'll take a look at O(n²). The best and most common example for this is a nested loop. Here's an example of a very simple nested for loop going through an array and returning all the possible pairs.
Taking a look at the graph for this function, we can see the larger the input, the time exponentially increases.
If we take a look at the equation, y =n² + an + c we can see that it's a quadratic equation. Remember that for O notation we're looking for the worst case scenario and the fastest growing term from the equation which is n² in this case. So our O notation for this function is O(n²). This makes sense cause the function is looping through our array twice.
Conclusion
Although O notation gets more complicated with more scenarios, hopefully this gives you a basic understanding of what it is and how it's measured. The biggest thing to remember is that O notation is a measurement of the worst case scenario. We're not so much interested in how time changes when you increase input from 4 to 5, but rather 4 to 1000, or even 10000. Here are some additional resources if you're looking to dive a little deeper into this topic.
https://www.youtube.com/watch?v=D6xkbGLQesk&list=PLK98i8lV22KFaHAsAj9aY-XzPX_i-Mz96&index=3
https://www.digitalocean.com/community/tutorials/js-big-o-notation
Top comments (0)