Big O Notation Isn’t That Hard
Big O notation is a big topic (see what I did there 🙂 ) in computer science, used to describe algorithmic complexity. MIT defines Big O as the following
Big O notation (with a capital letter O, not a zero), also called Landau’s symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions. Basically, it tells you how fast a function grows or declines.
From MIT’s website
Basically Big O notation breaks down how many steps an algorithm takes to complete. We use the letter O because we are finding the order of the function also called the rate of growth. As the input of a function grows, how does the function scale?
There are many ways to write an algorithm, but you want to always make sure your algorithm can perform the same with large input sizes as they do with small input sizes. This is why when analyzing an algorithm you count the number of steps it will take to complete said algorithm. Let’s take an example
function myLoop(n){
int x = 0;
for(int i=0; i < n; ++i){
x += n;
}
return x;
}This algorithmic complexity is O(n), why? It is O(n) also called Big O of n because this algorithm grows proportionally to the size of the input n. Let’s break down the steps.
int x = 0;
This is O(1) also called constant time because the computer will always take the same amount of time and resources to create an assigned variable. No matter if n = 100 or n = 100000, int x = 0 will always take the same amount of time.
for(int i=0; i < n; ++i){
x += n;
}We have to go through every element in n for this function. In this case we have to go through every element, then we are doing an addition which like variable assignment is constant time, so this analysis is O(n)+O(1).
So overall this algorithm runs O(1)+O(n)+O(1). We can drop the constants so this simplifies the algorithmic complexity to O(n).
Rule of thumb if you see a for loop you will more than likely have O(n) somewhere in your analysis. Every NESTED loop will add an exponent to your analysis so this would be O(n^2) because you have to go through the loop n^2 times
for(int i=0; i < n; ++i){
for(int i=0; i < n; ++i){
x += n;
}
}Big O Notation & Data Structures
Some of you have had the unfortunate experience of doing a technical interview and were asked to give the run time of the algorithm that you created and were stumped. The best advice I can give you is memorize and understand basic data structures. Most algorithms will use basic or variations of the most common data structures such as lists, queues, hash maps, etc. Knowing these and how they work will drastically reduce the complexity of technical analysis. I have a Big O notation cheat sheet that breaks down the complexities of common data structures. It really helped me and I know it can help you too!
Summary
Big O notation is just a fancy word for “How does this function scale as input increases over time”. In this blog I gave a theoretical overview into what Big O is and in my next post I will do more deep dives into data structures and break down their algorithmic complexity. Big O isn’t something you are going to get on the first try or first attempt so I will be breaking it down into bite size chunks and we will go forward a blog at a time!
