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 :

1. 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

2. 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 )

3. Quadratic: O( n² )

   same as linear but run n² times for n input

4. Cubic: O( n³ )

   takes n³ times to execute n number of input means program run triple X times for x input

5. Logarithm : O( logn )

   For this we need to know what log function do it actually divide the input 2

   

6. Exponential: O( 2^n )

   Grows exponentially very fast

   Example : O( a^n ),O ( 3^n )

7. Factorial: O( n! )

   Grows even faster than exponetial makes program slow

Example:

1.  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)