Hello everyone! 😁
Hope you’ve enjoyed the starters and how it’s time to dig in the main course. Do you remember the first complexity of Big O? Yes! It’s O(n)! Today, I’ll tell you about the remaining complexities: O(n^2), O(1) and O(log n). Let’s get started…
What is O(n^2)?
A simple Java code will aid us to understand the concept of O(n^2):
As you can see in the code above, there are two ‘for’ loops, one nested in another. We know that a for loop generally represents O(n). So, here there will be two O(n) which lead to n*n = n^2.
This in short will be represented as the second complexity of Big O – O(n^2). This is known as the least efficient complexity and if your code has the complexity of O(n^2), then you should try and make an effort to either change the code or the algorithm. 😬
What is O(1)?
If you recall, in O(n), the growth in number of operations is directly proportional to the value of n. So, if let’s say, n has the value of 100, there will be 100 operations performed by the code.
However, with the third complexity of Big O – O(1), there is only one operation. That is the main reason why O(1) is the most efficient complexity.
What is O(log n)?
The fourth complexity of Big O – O(log n) generally means that any specific operation you apply to a data structure (like insertion/deletion/searching) would take logarithmic time. In simple words, each time the number or size of input would be reduced to half of its previous value.
Let’s take an example of an array of 10 numbers like - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Assume we need to search for 9 in this array.
We start with the middle element of the array i.e., 5 and check whether our number is greater than or smaller than the middle element.
Since 9>5, our new array would contain all the values greater than 5 since we don’t need numbers lesser than 5.
New array would be like - 6, 7, 8, 9, 10
Applying the same procedure above and taking 8 as middle element, our new array would be - 9, 10.
Now in the next step, we would find our number 9 since there are only 2 numbers left.
So, rather than going all the way from 1 to 9, we reduced our search at each step into half in order to find our element.
This kind of time complexity where at each step our input is reduced to half is known as O(log n) time.
Efficiency order:
O(n^2) < O(n) < O(log n) < O(1)
Well, I hope the concept of each complexity of Big O is clear in your mind. When working in the field of computer science, it is always helpful to know such stuff (and is quite interesting too). Who knows, maybe you’re the one in your team who is able to find an optimized solution for a problem, just because you know what you’re dealing with. 😎
“Writing code is good, writing code that works is better, writing optimized working code is best.”
And this is where, my dear readers, the main course ends. I hope you truly enjoyed it and are excited for more. If so, do drop ❤️ and I’ll see you soon in my next blog. Till then…
Learn, Share, Grow!
Bye!