Time Complexity Simplified….

In the previous blog I had proved how Time Complexity plays an important role in developing an optimised algorithm, in this blog I will tell you everything about Time Complexity.

This is the only guide you need to understand Time Complexity in Simplicity.

What is Time Complexity??

Time is very precious to every being, we manage all our day to day task by assigning a fixed amount of time. Same goes for Computing Devices also, a fixed amount of space and time will be given for an algorithm or a task to run by our memory systems.
Time complexity tells you how fast or slow an algorithm runs corresponding to the input given.

Notations of Time Complexity

We denote it in three different terms.

Big-oh Notation (Worst case)
Theta Notation (Average case)
Omega Notation (Best case)

When asked to find Time Complexity, we generally find for the worst case scenario until asked specifically.

Consider you are finding an element in an array. So, you will use bubble sort algorithm to find the element.

Best Case - When the search element is present at the starting of the array ( no need to go through all the elements in the array).

const array = [x, 1, 5 ,8 ,10];

Average Case - When the search element is present somewhere at the middle of the array( you need to go through half of the elements in the array).

const array = [5, 1, x ,8 ,10];

Worst Case - When the search element is present at the end of the array ( you need to visit all the elements in the array).

const array = [10, 1, 5 ,8 ,x];

How to find Time Complexity??

Step 1 :- Write an equation for the given algorithm by identifying the Basic Operations ( comparisons, assignments, loop iterations).

Step 2 :- In that Equation ignore the constants and lower terms and identify how many times is this particular operation is being executed.

Step 3 :- And booommm… You have the Time Complexity of your algorithm.

Refer below to identify the lowest terms to terminate them in the final equation..

💡

1 < log n < n < n log n < n² < n³ < a^n < n!

Common Types of Time Complexities

Constant Time - O( 1 )

Here the time is constant i.e, it does not change with input size.

Generally time is constant when declaring variables, assigning values.
```
 const x = 19;
 const y = 10;
 const z = x + y;
 console.log(z);
```
Linear Time - O ( n )

Time grows with Input size. Mostly represented when loop is used.
```
 const n = 5;                     // ==> O(1) 
 for(let i = 0; i < n; i += 2){   // ==> O(n/2)
     console.log("Chai aur Code"); // ==> O(n)
 }
```
Equation we get here is, O(1) + O(n/2) + O(n), after removing the constants and ignoring the small terms, we get O(n).
Quadratic Time - O(n²)

This is same as Linear Time case, but is represented when there are nested loops
```
 const n = 4;
 for(let i=1; i<n; i++){    
     for(let j = 1; j < n; j++){
         console.log('I =',i,'J =',j);
     }
 }
```
The outer loop runs for n times, so as the inner loop, and the log statement inside the inner loop runs for n * n time i.e, n² times == O(n²) is Time Complexity for the given algorithm.
Logarithmic Time - O( log n )

When the loop jumps in longer steps. Time grows very slowly even for large inputs. Usually found in divide and conquer algorithms
```
 const n = 4;
 for(let i = 1; i < n; i =* 2 ){  // can be also implemented for i =/ 2
     console.log('I =',i);
 }
```

Linearithmic Time - O( nlogn )

Time Complexity that grows faster than linear (O(n)) but slower than quadratic (O(n²)). It occurs when an algorithm performs a logarithmic operation (log n) for each element (n).

 const n = 4;
 for(let i = 1; i < n; i++ ){          // O(n)      
     for(let j = 1; j < n; j =* 2){    // O(logn)
         console.log('I =',i,'J =',j);
     }
 }

So this is how you basically find out the Time Complexity of your algorithm…EASY RIGHT??? yessssss!!!

Conclusion

Just find the Basic Operation in the algorithm, and make an equation out of it. Then terminate the constants along with the small terms
There you goo..you got your Time Complexity of your Algorithm.

Time Simplicity