Time Complexity: It is basically an estimate about the time taken a an algorithm to run. It is measured by counting the number of basic operations performed by the computer.
Asymptotic Analysis : Asymptotes: In analytic geometry, an asymptote of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the x or y coordinates tends to infinity. On similar lines, asymptotic analysis implies checking the performance of an algorithm when the input size keeps on increasing.
There are 3 notations :
- bigo(n)
- Omega(n)
- theta(n) For practicality, we are always interested in finding the upper bound of an algorithm hence we only find bigO(n)
Some general time complexities and their intuition :
- log(n):
we know log(8) is 3. In computer Science, we always deal with log to the base of 2
we can also say that (((8/2)/2)/2) or in words when we divide 8 three times then the answer that we get is again 3
so what does this mean? Whenever in our algorithm we only are taking into consideration one half of the input size then the time complexity will automatically be log2(n)
Example: Binary Search In binary search, we always consider only one half of the array and ignore the second half of the array hence the time complexity is log(n) Similar is the case for binary search trees. We only search only in one subtree of the tree that is either in the left or in the right subtree
- o(1) : it indicates that our algorithm has no dependency on the size of the input. Or in simple words irrespective of the change in the input size it does not affect the performance of the algorithm
Example: using a for loop for a fixed number of times
O(n): It indicates that as the size of the input increases so does the time taken by the algorithm increase at a linear rate.
O(n^2): It indicates that the time taken by the algorithm is directly proportional to the square of the input size
Cheat Sheet for accepted time Complexity vs the input size given
In the above image left-most column refers to input size and the right most accepted time complexity.
This is calculated as: Most computers these days are capable of performing 10^7-10^8 operations in one cycle. Hence substitute the value of n ( input size ) which will be given in the question and check if the algorithm designed follows the 10^7-10^8 rule. This means that after substituting the value so obtained should be in the 10^7-10^8 range else we will get time limit exceeded error