Continuing Types of Big O Notation

Big O(n^2)

Hello guys if read my previous article about Big O notation and its two types then this article will be lot easier for you to understand what is Big O(n^2).

O(n^2) is one if the type or ways of Big O notation using which we can calculate time complexity of any algorithm or piece of code.

In above example we have used nested loops as we already know we are executing multiple operations or no. of input in this case nested for loop is getting execute multiple times using for loop so that operation complexity will be O(n).

Inside that for loop we have used another for loop which nested one which is also doing same operation no. of times and therefore based on no. of input processed by for loop we are calculating its time complexity which is O(n).

Now the time complexity of this method is O(n*n) which get simplified and we get O(n^2).
We can say this algorithm runs in Quadratic Time. Now lets understand what it means.

Our method was linear when we were having only one operation or number of inputs like O(n) or O(1) because that time our method was increasing linearly as per involving inputs; meaning the time required to run that algorithm or computational effort to run that algorithm was proportional to N.

But when we took nested for loop at that time computational efforts or time will get increases as the square of number of input.

What it concludes is algorithms which runs in O(n^2) are slower than algorithms which runs in O(n).

The Effect of it cannot be seen for lower no. of inputs but when inputs gets larger and larger this O(n^2) algorithm gets slower.

In above example we have added extra for loop at the beginning and its time complexity is O(n).

we have dropped n because the n^2 is greater itself or we can say n^2 grows faster than n which is why n doesn't gonna make big difference if we added it to n^2 and that's why our final time complexity for our algorithm was O(n^2).

Now lets see one more example what if we take another nested for loops inside existing one.

As you can see runtime complexity of this algorithm is O(n^3) and now it is more slower than O(n^3).

O(log n) is another type of Big O Notation lets understand it; It helps to calculate another growth rate which is logarithmic growth rate.

If we compare O(log n) with our algorithm which runs in linear time or grows in linear time then we will understand that logarithmic which O(log n) is faster than linear O(n) or quadratic algorithm (n^2).

This type of big O notation is known as logarithmic runtime algorithm which is faster than linear and quadratic time algorithms.

If we take array of 10 elements and search no. 7 in it then it will have to search for every no. to get it till no. 7 comes this is linear search (linear algorithm)
where as if we do same operation using logarithmic algorithm like binary search it will reduce no. of comparisons between all elements by taking their medium.
it will check given no. is greater or lower than searching no. if it is lower then it will search only right portion of that medium no. we selected and that's how we get our output.

Only disadvantage of this big O(log n) notation is that as input increases our logarithmic algorithm get slows down.

This notation or run time complexity of such type of algorithm is opposite to logarithmic growth rate or algorithms.

At initial level it is very fast but once input get increases that soon it get slower and very much slower than any type we have seen so far.

For comparison i have given one screenshot which will let you compare with other growth rates or runtime complexity.

We will see about it in much deeper in separate article for now we will see up to this point.