**Time and Space complexity **is a very important part of Data Structure. Less time and space complexity makes our program more efficient. While writing any program you must consider time and space complexity as the primary requirement. If you write a program having more time and space complexity it makes your program bulky. It is important to minimize the time and space complexity as much as it is possible.

**Time complexity**

**Time Complexity **is defined as the time taken to execute each statement of the algorithm. Time and space complexity can be estimated by the number of elementary operations performed by the algorithm. We use Asymptotic Notation to express the time complexity. Time complexity is most commonly expressed using **big O notation. ****https://en.wikipedia.org/wiki/Big_O_notation**

```
Example 1:
int main () {
printf ("Hello, World!"); // time complexity O ( 1 )
}
```

In** Example 1 **there is a single statement that takes a unit of time to execute. The *T*ime complexity of this program is **big oh (1).**

```
Example 2:
int main () {
int number = 5; // time complexity O(1)
if (number < 0) { // time complexity O(1)
printf ("You entered %d.\n", number);
}
printf ("The if statement is easy.");
}
```

In **example 2** each statement takes a unit of time to execute. The time taken by the **if, if else and else statement **is **0(1). **Hence the overall Time complexity of the whole program is **0(1).**

```
Example 3:
int main(){
int length=11;
int i ;
for (i = 1; i <= length ; ++i) //time complexity O(n)
{
printf ("%d ", i);
}
return 0;
}
```

In **Example 3** output is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11. **For loop,** the statement is run 11 times the for printing required output. If the Length is N then For statement run N times for printing required output. Hence the Time complexity of For loop in **0(n);**

```
Example 4:
int main()
{
int i, j;
int matrix[ROW][COL] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
printf ("Given matrix is \n");
for (i = 0; i < ROW; i++) { // time complexity 0(n)
for (j = 0; j < COL; j++) { // time complexity 0(n)
printf ("%d ", matrix[i][j]);
}printf ("\n");
}
return 0;
}
```

In **Example 4** there are two loops that are used to print **2D Array** as we know one **For loop** takes **0(n)** time. In the case of nested loop **0(n*n) = 0(n^2) **for two nested loops. Similarly, a single while loop takes **0(n)** time.

```
Example 5:
int binarySearch (int array[], int x, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
```

In **Example 5** as we know while loop takes 0(n) time and every time the size becomes half. The make-time complexity reduces and becomes **0(log n)**.

Algorithm | Time Complexity |

linear Search | O (n) |

Binary Search | O (log n) |

Bubble Sort | O ( n^2) |

Selection Sort | O ( n^2) |

Insertion Sort | O ( n^2) |

Merge Sort | O (n log n) |

Quick Sort | O (n log n) |

**Space complexity**

**Space complexity **is defined as the number amount of **memory used **by your program. As an application user, I want that what application I use takes less time as well as less space. Hence it is important to use the minimum possible space for reducing the space complexity. For Example, when we create a stack and queue we required additional space, and in programs where we use hashing required extra space.

```
Example 1:
int add
int addNumbers(int n) {
if (n != 0)
return n + addNumbers(n - 1);
else
return n;
}
```

Here each function call adds extra space to the stack and makes their** space complexity 0(n).**

** Note**: It is necessary to mention that Space complexity depends upon a variety of things such as programming language, compiler, or even the machine running the program.