WHAT IS COMPLEXITY?

The measurement of the efficiency of an algorithm is termed as COMPLEXITY in terms of TIME and SPACE resources.
It helps the user evaluate and analyse the performance and efficiency of the algorithm.

`Time Complexity :`

Time complexity is the way to analyse how the runtime of an algorithm changes as the size of the input increases.

In simple words, time complexity refers to the time taken by the algorithm to get executed.

`Time Complexity is Expressed using Big O Notation :`

O(1) → Constant time
O(log n) → Logarithmic time
O(n) → Linear time
O(n log n) → Logarithmic time
O(n²) → Quadratic time
O(2^n) → Exponential time

Let’s understand this using an instance :

for(int i = 1 ; i <= 10 ; i++) {
    for(int j = 1 ; j <= 10 ; j++) {
        cout << i << j ;
     }
  cout << endl;
}

In the above program snippet, the time complexity is 10 × 10, which is 100. In other words, the time complexity is O(n²) , where n is the number of iterations.

`How the time complexity is 100?`

Firstly, the outer loop will execute 10 times.

Secondly, the inner loop will also execute 10 times.

Finally, the time taken by both loops is multiplied because they are nested loops, meaning they depend on each other.

`Space Complexity :`

Space Complexity is the way to analyse the amount of space taken by the algorithm to get executed.

In simple words, the amount of space taken by the algorithm is Space Complexity

Space complexity can also be termed as Memory Complexity.

`Space Complexity is Expressed using Big O Notation :`

O(1) → Constant space
O(n) → Linear space
O(n²) → Quadratic space

Let’s understand this using the same instance of Time complexity :

for(int i = 1 ; i <= 10 ; i++) {
    for(int j = 1 ; j <= 10 ; j++) {
        cout << i << j ;
     }
  cout << endl;
}

In the above program snip-it the space complexity will remain constant which is O(1) .

`How the space complexity is constant?`

As we can see in the code snippet, only two variables have been declared, which are i and j . If we talk about the cout keyword, it only prints the value, so it is not considered an element that takes space in the algorithm.

The space taken by i and j is fixed, which is why the space complexity of the above program snippet is constant.

Complexities In Data Structure Algorithm

Table of contents