# The complexity of an Algorithm :

There are two types of complexities of an algorithm. One is time complexities and another is space complexities.

**Time complexity:**

In computer science, the time complexity is of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representation the input. The time complexity of an algorithm id commonly expressed using big O notation, which excludes coefficients and lower order terms. When expressed this way , the time complexity is said to be described asymptotically, ex : input size goes to infinity.

For example, if the time required by an algorithm on all inputs of size n is at most 5n^{3 } + 3n, the asymptotic complexity is O(n^{3}).

**O(1) Constant Time:**An algorithm is said to run in constant time if it requires the same amount of time regardless of the input size.

** Examples : **

- array: accessing any element
- fixed-size stack: push and pop methods
- fixed-size queue: enqueue and dequeue function.

Input (x) | O(1) |

a = 10 | O(1) |

a = 1000 | O(1) |

**O(n) Linear Time:**

An algorithm is said to run in linear time if its time execution is directly proportional to the input size, i.e time grows linearly as input size increases.**Examples :**

- Array : Linear Search,Traversing ,Find minimum etc.
- ArrayList : Contains method
- Queue : Contains method

Looping (for,while,repeat) Running time for this statement is the number of lopping multiplied by the number of operations inside that looping.

```
for(int i = 0;i<n;i++){
//do something
}
for(int i =n;i>=1;i--){
//do something
}
```

**O(log n**^{2}) Quadratic Time :

An algorithm is said to run in quadratic time if its time execution is proportional to square of the the input size.

**Examples: **

- Bubble Sort
- Selection Sort
- Insertion Sort

```
for(int i = 1;i<=n;i++){
for (int j =1;j<=n;j++){
//do something
}
}
```

**O(log n) Logarithmic time :**

The time complexity of a loop is considered as O(log n) if the loop variables are divided or multiplied by a constant amount. An algorithm is said to run in logarithmic time if its time execution is proportional to the logarithm of the input size. Example: I divide the class into two groups, then ask,” Is it on the left side of the right side of the classroom” then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen, This is what you mean by** O(log n).**

**Example:** Binary Search

```
while(l<=h){
mid = (l+h)/2
if(target < list[mid]){
h = mid -1
}
else if(target > list[mid]){
l = mid + 1
}
else {
break
}
}
```