Big O notation
Big O notation is simplified analysis of algorithm’s efficiency. Big O gives us some algorithm complexity in term of input size n and give us abstract of machine the code on which run .We can use big O to analyse the time and space . There are couple of ways to analyse the algorithm efficiency we can analyse the
1- Worst case
2- Average case
3- Best case
Few general rules for big O notation
1- Big O notation ignore constants.
2- Certain terms ‘dominate’ on the others
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<)(2n)<O(n!)
Ignore the low order terms when you dominate the high order ones .
This chart can be found on bigcheatsheet.com along with handy guide on big O various important algorithms .Lets do some simple examples to analyse more . Start with constant time. Imagine we have following lines of code
x= 4+(12+25);
Its basic statement compute the x and notice it doest not depend on the input size in any way .We can call it Big O(1) or constant time .
What happened when we have sequence of steps ?
x= 4+(12+25);
Y= 14–4;
print X+Y;
Notice that all steps are constant time how could be compute big O for this block of code .We simple add each step time and we get three multiple by Big O of 1 . So remember we drop constant so its big O(1).
total time = O(1) +O(1)+O(1) = O(1)
I hope this gives you the understanding of Big O notation . Lets talk about the real world practice when you create the algorithm please realize that constant absolutely do matters.so constant of two or three could have a large impact on your code .
