Big O is one of the most asked questions in technical interviews. It is the upper bound of the run time of an algorithm and is one of the most commonly used criteria to check the efficiency of an algorithm. In general big O is taken as the “minimum upper bound” of an algorithm but an algorithm having O(n) can also be said to have O(n*2) as this upper bound is also correct but has no use. So the minimum upper bound is the one used in industry and serves as the scale to measure algorithm’s efficiency.
Most common types of big Os are O(1), O(logn), O(n), O(nlogn), O(n^2) and O(2^n) where n specifies the input dataset.
Now let’s go into explanation of
The run time of an algorithm having a constant big O like this doesn’t depend upon the size of input. Take the example of a simple algorithm which takes a number as input and just prints it out. Now, no matter how big is the input, the runtime will always be the same. We call this type of algorithm to have a constant run time complexity or in other words we say that this algorithm has O(1).
An algorithm having O(logn) is usually a divide and conquer algorithm for example binary search. The run time in this case do depend upon the size of input but it doesn’t traverse all the inputs instead it divides it and hence cuts off the run time.
This is a linear time algorithm meaning its time complexity graph is linear. Its time of execution increases in proportion with the length of the input. Take example of a program which prints numbers from 1 to n. It’s run time will be O(n) which increases with n.
A divide and conquer algorithm which performs additional operations along with divide and conquer has a run time complexity like this. Take example of merge sort which divides an algorithm but the merge step takes additional time and hence bigO of nlogn.
< h2 >O(n^2), O(n^3), O(n^4) …
An algorithm which traverses its input for each element of its input will have a run time complexity of O(n^2) as in the case of two nested loops that go from 1 to n. Similarly an algorithm with three nested loops each from 1 to n will have a O(n^3) and so on.
An algorithm has bigO of 2^n if its growth doubles with each addition to input dataset. An example is the recursive algorithm to find Fibonacci.