 # What is Time Complexity || Complete Guide

As we discussed in our previous post, analysis of algorithm we know on which factor the time complexity of the algorithm depends

1. Machine
2. Algorithm Speed

We know, on our hand, we can control only algorithm speed Machine and its speed may vary.

So, In this post, we are going to learn time complexity which is an important tool to know algorithm running speed.

## What is Time Complexity

The time complexity of an algorithm or a program is the amount of time it needs to run to completion.

The exact time will depend on the implementation of the algorithm, programming language, optimizing the capabilities of the compiler used, the CPU speed, and other hardware characteristics/specifications and so on. However, to measure the time complexity accurately, we have to count all sorts of operations performed in an algorithm.

The time complexity also depends on the amount of data inputted to an algorithm.

We learn each topic in easiest way possible.

## Units of measuring Time Complexity

### Asymptotic Notation

Asymptotic notations are mathematical tools to represent the time complexity of algorithms for asymptotic analysis. The following 3 asymptotic notations are mostly used to represent the running time of algorithms:

Now, we are going to learn three asymptotic notation one by one to analyze the running time of the programme

##### 1. O Notation(Big- O)

O Notation is the simplest and most used asymptotic notation. It is the upper bound of the algorithm, what is upper bound? Upper bound means the running time of program can not go beyond this time

let’s take an example, assume we say that the Big-O Notation of Linear search is n where n is input size then this simply means this is the upper bound and if we run our program, running time do not go beyond n

``````O(g(n)) = { f(n): there exist positive constants c and

n0 such that 0 <= f(n) <= c*g(n) for

all n >= n0}``````

From Above All, Notable Point’s are

1. Big O notation always point to the worst-case scenario
2. Maximum Time
3. Upper Bound
4. Most Used
##### 2. Ω Notation(Big- Omega)

As we know Big O notation provides an asymptotic upper bound on a function. However, Ω notation provides an asymptotic lower bound.

Big – Omega Notation can be useful when we have lower bound on the time complexity of an algorithm. This is the least used notation.

``````Ω (g(n)) = {f(n): there exist positive constants c and

n0 such that 0 <= c*g(n) <= f(n) for

all n >= n0}.``````

From Above All, Notable Point’s are

1. Best-case scenario
2. Minimum Time
3. Lower Bound
4. Least Used
##### 3. Θ Notation (Big-Theta)

Above all, we learn the upper bound and lower bound. In addition, there is also Big Theta which shows an average of these two.

The theta notation bounds functions from above and below, so it defines exact asymptotic behavior.

From Above All, Notable Point’s are

1. Average-case scenario
2. Average Time
3. Average Bound
4. Least Used
``````Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such

that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}``````

### Important Points in Time Complexity

• Most of the time, we do the worst-case analysis to analyze algorithms. In the worst analysis,Therefore, we guarantee an upper bound on the running time of an algorithm which is a good piece of information.
• The average case analysis is not easy to do in most of the practical cases and it is rarely done. However, the average case analysis, we must know (or predict) the mathematical distribution of all possible inputs.
• The Best Case analysis is bogus. Guaranteeing a lower bound on an algorithm doesn’t provide any information as in the worst case, an algorithm may take years to run.

In Conclusion, Big O is mostly used and Most Important

## Examples

Let’s see some examples, to understand the time complexity.

### Example 1

``````
#include <stdio.h>
int main()
{
printf("Hello World");
}``````

For the above code, the time complexity is O(1). This is because, the hello world will be printed only once and hence this is a constant. That’s why it is O(1).

### Example 2

``````#include <stdio.h>
void main()
{
int i, n = 8;
for (i = 1; i <= n; i++) {
printf("Hello Word !!!\n");
}
}``````

For this code, the time complexity is  O(N). This is because the for loop runs for around n times and therefore time complexity is O(N).

### Example 3

``````//sum of two numbers
Sum(a,b){
return a+b  //Takes 2 unit of time(constant) one for arithmetic operation and one for return.(as per above conventions)   cost=2 no of times=1
}``````

Tsum= 2 = C =O(1). This is because in the code it is specified as 2 unit of time. We always ignore the constant and so, this becomes O(1).

### Example 4

``````//sum of n numbers
list_Sum(A,n){//A->array and n->number of elements in the array
total =0           // cost=1  no of times=1
for i=0 to n-1     // cost=2  no of times=n+1 (+1 for the end false condition)
sum = sum + A[i]   // cost=2  no of times=n
return sum         // cost=1  no of times=1
}         ``````
```Tsum=1 + 2 * (n+1) + 2 * n + 1
= 4n + 4 =C1 * n + C2
= O(n)```

I hope the explanation is clear from the steps itself as it is very easy.

## Conclusion 