Time Complexity Explained

What is time complexity ?
Time complexity is time taken by the code or algorithm to execute the program.
Time complexity depends on the size of the input.
There are three notations in time complexity :
Best Case ( Ω ) | Average Case ( Θ ) | Worst Case ( O ) |
Why it is important to calculate time complexity ?
So that we can optimize the program and make it faster by reducing its time complexity
How to calculate time complexity ?
Generally we calculate the worst case by default if not ask because it the program is running fast and we can use it for high input size then it will be definitely can manage less input size
We ignore constant from the equation that comes like n/2*logn => nlogn
To calculate we create equation of the program the calculate it like :
Constant : O( 1 )
when the algorithm irrespective of the input size takes same time to execute the program is known as constant time complexity
It take same time for best , average and worst case
Linear: O( n )
when the program runs n times for n number of input like if we give 8 different input then it will run 8 times in worst case i.e o( n )
Quadratic: O( n² )
same as linear but run n² times for n input
Cubic: O( n³ )
takes n³ times to execute n number of input means program run triple X times for x input
Logarithm : O( logn )
For this we need to know what log function do it actually divide the input 2
Exponential: O( 2^n )
Grows exponentially very fast
Example : O( a^n ),O ( 3^n )
Factorial: O( n! )
Grows even faster than exponetial makes program slow
Example:
int main() { int a, b, c, n; a = b + c; // O(1) → constant time for (int i = 0; i < n; i = i + 2) { // Runs n/2 times → O(n) for (int j = 1; j < n; j = j * 2) { // Runs log(n) times → O(log n) c++; } } return 0; } // show its time complexity is O(nlogn)
Subscribe to my newsletter
Read articles from Mayank Mahajan directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
