If you're in the computer science field or somehow connected to it, you might have heard a term called Big O notation used especially when it comes to data structures and algorithms. Knowing what this means is also very crucial for a job interview as a software engineer!
Today let's understand everything you need to know about Big O notation so that you can answer any question related to this topic whenever asked in an interview.
What is Big O notation
Big O notation is a way to represent the time and space complexity of an algorithm! From this definition, things got more confusing than before because now we have three new terms to understand to fully digest the concept of Big O. Let's understand one by one!
What is an algorithm?
An algorithm is a set of instructions for solving a problem or accomplishing a task. For example, If you're hungry and you want pizza what would you do? Simply open up your smartphone, Go into the domino's app and place an order! If you noticed to get the pizza you have to follow certain steps. This process of following certain steps to achieve an objective is called an algorithm in technical terms.
What is time complexity?
The total time taken by the algorithm to complete the execution is called time complexity.
What is space complexity?
The memory occupied by the algorithm is called space complexity.
Importance of Big O notation?
Therefore Big O is a way to represent the time and space complexity of an algorithm. Hope now that made much more sense. But the question is why do we need to show the time taken and memory occupied by an algorithm? At the end of the day, work is done then why Big O plays such an important role?
I remember my professor use to say that in computer science there are at least two possible solutions for any problem. And that's true! There can be "n" number of ways to solve the same problem, but we don't just need the work to be done on the compromise of efficiency! We need work done most efficiently. So, how can we measure the efficiency of an algorithm? Yes, you guessed it right using Big O notation.
So, why companies are so concerned about the Big O notation anyways while interviewing?
The answer is that Big O notation makes you learn the concept of efficiency in your code. So when you would work with massive data, you will have a fair sense of where downshift are likely to cause bottlenecks, and where more attention is required to get the largest improvements.
Type of Big O notations
There are mainly 6 types of Big O expressions.
- O(1) - Constant time
- O(log n) - Logarithmic time
- O(n) - Linear time
- O(n log n) - Linearithmic time
- O (n ^ 2) - Quadratic time
- O (2 ^ n) - Quadratic time
- O (n!) - Factorial time
These types are arranged in order so that the first one is the best and the last one is the worst case. This can be better understood using the below image.
Examples of Big O rating calculation
- Numeric example
Let’s work through a numeric example. If an algorithm has the number of operations required formula f(n) = 6n^4 - 4n^1 + 5, then let's find out its Big O rating.
Firstly there are three terms 6n^4, 4n^1, and 5. Since "n" approaches infinity (for very large sets of data) only the largest "n" value matters therefore we are only concerned about 6n^4. Also, we'll omit the 6 because constants in calculating Big O are insignificant.
Therefore, this algorithm would have a Big O(also referred to as order growth rate) rating, of O(n^4).
- Programming example
Let’s work through a programming example. Say we want to print a right-angle triangle. The code would look something like this
class RightTrianglePattern {
public static void main(String[] args) {
for(int i = 0; i < 5; i++) {
for(int j = 0; j <= i; j++) {
System.out.print("@");
}
System.out.print("\n");
}
}
}
So, there is a total of two loops that means we can find a Big O rating for both of them one by one and then merge it to get the final result.
First, let's find the Big O for the inner loop. The loop executes for "n" number of times as we can see in the for loop's condition expression. Therefore, the Big O would be O (n).
Now, let's do it for the outer loop. Same as the inner loop, the outer loop executes for "n" number of times. Therefore Big O would be O (n).
Finally, we'll merge them. So the inner loop executes "n" number of times for a single iteration of the outer loop. Therefore the final Big O would be O (n) * O (n) = O (n^2).
Conclusion
Finding Big O rating from the formulas or code directly is kind of like solving math problems, you need practice. So, find yourself some algorithms and try finding the Big O rating for each of them.
Bonus Big O cheatsheet
All images here are from Big O Cheatsheet
And also
I'm not just a blog writer. I create content in various formats so don't forget to check my other social handles!
Top comments (0)