What is time complexity?

It is a rough idea on how “Time taken by program to execute” increases with input data.

```
How to calculate it?
```

You can roughly approximate it as highest growing function in the expression.

Eg, consider 2 loops-

```
for(i=0;i<n;i++)
for(j=i;j<n;j++)
```

Its clear that in above, for first iteration of outer loop, inner loop executes N times, then N-1, then N-2…upto 0.

Total operations = N+(N-1)+(N-2)…+0 = N*(N+1)/2 = 0.5 x (N^2)+ 0.5 x N. The highest growing function here is N^2, so we call it O(N^2).

Similarly, if after analyzing your code you get function F= 2^n +N* N, then the time complexity is O(2^N). The lower powers are considered negligible compared to highest power, especially when N gets large.

```
What is the benefit of knowing and calculating time complexity?
```

You can find out before hand if your will get TLE or not. Judge machine can perform ~5 x 10^7 instructions per second (vary from site to site). If your complexity is O(N^2), and N can be upto 10^5, then it means that your code needs ATLEAST (10^5)^2 = 10^10 operations to give output. Divide by number of iterations per second, we see your code needs hunders or thousands of seconds to run, hence its too slow.

```
What is worst case scenario, best case scenario and average case scenario in time complexity?
```

Worst case scenario means, the type of test case where your code needs most time to run. Eg, take example of finding element X in array. If we find it in array, we break out of it and print “Found”. But what if X is last element, or not present at all? We will have to look through entire array in this case. This is worst case for our code, as we have to travel ENTIRE array. Similarly, X being somewhere in start is best case, as we are able to break earlier and save operations if X is found in start.

Average is pretty much, the average time taken.