Introduction
When I was first learning how to program, I kept running into the term “Big O notation”. If I was on Stack Overflow trying to figure out a problem I had, or I was looking at “better” answers to Leet Code problems, I was constantly running into this term.
So, I decided to search it up. After reading the Wikipedia definition of it, I found myself even more confused than before.
“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity”
What does this mean, and what does it have to do with programming? The confusion then morphed into curiosity, and I decided to finally understand what Big O notation was really all about.
Simply put, the Big O notation means how fast will my program run. This post will cover the three most common notation types a beginner will use: O(1), O(N), and O(N²).
O(1)
To start us off, let's go over O(1). O(1) means that no matter what the size of your input data is, it will take the same amount of time to run your program.
def is_first_element_1 (your_input):
return your_input[0] == 1As we can see here, no matter how big of an input we give this function, the output will always be the same speed.
O(N)
Next, let’s cover O(N). O(N) basically means that as your input size increases, your output speed increases at the same proportion (linearly). For example, your program takes 1 second if the input size is 1, 2 seconds if the input size is 2, 3 seconds if the input size is 3, etc., your algorithm is O(N). Generally speaking, this is a good first iteration of your program, and you can refactor it down later.
def list_total (your_list):
total = 0
for number in your_list:
total += number
return totalLooking at the example above, as your input list grows, the amount of time it will take the program to run will also grow at the same rate.
O(N²)
Finally, let's go over O(N²). An algorithm is classified as O(N²) when your output time is squared to your input. A common example of running into O(N²) is when there is a nested loop in your algorithm. If you notice that your program has a speed of O(N²), it would be a good idea to clean up your code. Having O(N²) might not seem that bad if you have a small input size, but it will take longer and longer to run your code as your input size increases. If possible, it is wise to avoid having an O(N²) in your final version of your program.
def nested_loop (your_input):
results = []
for num1 in your_input:
for num2 in your_input:
results.append(f'your number saved here {num1} and here {num2}')
return resultsIf you run this code, you will see that that it will run the second for loop on every instance of the first for loop. This means that if you run a list of 100 elements, the second for loop will run 100 times for every instance of the first for loop. This will drastically slow the speed of your code as your input size increases. One last thing to note, each time you nest another loop, the O(N²) will increase. For example, if another nested for loop was added, the Big O notation would actually be O(N³).
Speed Graph
The graph below visualizes the different speeds at what each Big O notation runs at, and if it should be used. Note: this graph contains more notations than I covered above, but more on that down below.
Conclusion
To sum it up, O(1) means that no matter how big your input size is, your output speed stays the same. O(N) means that as your input size increases, your output speed increases at the same rate. O(N²) means that as your input size increases, your output speed will slow down drastically. While there are ways to calculate what your O notation currently is, it is more common to think of Big O as a concept rather than an equation. Try reading through your code and estimate how fast it will run!
While extremely watered down, I hope this brief introduction has helped with your understanding of Big O notation. When first learning this, it is quite easy to get overwhelmed with all of the different notations and best use cases, so I hope this high-level approach has helped. If you are interested in learning more about Big O notation and seeing the other notations it contains, I recommend checking out the links listed below.