Big O Notation

I want to explain it in a few simple words. Basically this is a tool to express how efficient your algorithm is. One point we need to remember that, the efficiency of an algorithm is very much relative, because it depends on many other factors like number of programs or process is currently running, the memory usage and on the specification of the system.

So, there must have been a method or a way so that we can express the efficiency of an algorithm independently and this can be done with the help of Big-O. Basically Big-O takes the number of operations present in an algorithm and also the size of it’s input. One thing to remember, we are concerned here only for the upper bound or for the worst case situations. e.g.

int findSum(int n) 
{ 
   int sum = 0; 
   for (int x=1; x<=n; x++)  
     sum = sum + x; 
   return sum; 
} 

In the above piece of code, we are finding the sum of the given numbers. Here the different operations are, assignment (sum = 0, x=1) which are out side the loop and independent of the numbers of input. And the comparator (x<=n) , increment (x++) and assignment with summation (sum = sum+x) inside the loop. But, if the the value of n becomes very large, then this all operations literally will depend on the value of the input. Because, the number of operations (2+4n) will become as only n. So here the BIG-O is O(n), which is a linear function.

So, this is the benefit to use the Big-O notation. As we can grossly explain how efficient our written algorithm is and which is quite correct.

But the catch is, there is not present any kind of best algorithm, because it varies greatly depending on the number of input. So, always adjust your logic of algorithm based on your inputs.