COMPLEXITY ANALYSIS

Don't get panicked by the term 'Complexity'.

Trust me! It is not as complex as it sounds.

Complexity Analysis of an Algorithm

Complexity Analysis can be of two types :

Time Complexity
Space Complexity

At first, let us understand Time Complexity with the below example.

Example :

Say, you wanted to go to your friend's home. And there are two routes that leads to your friend's home. The first route is just 1 KM and the second route is 3 KMs.

So, which route would you choose?

Definitely, the first route that is 1 KM. Because it is the shortest and it would take lesser time for you to reach.

And the same thing is applicable for Algorithms as well. The Algorithm that takes lesser time would be preferred by everyone.

Just imagine, what if google would be taking 2 minutes to show search results. Would you ever accept it?

No right!

Google can only return search results within a fraction of second, because of an efficient Algorithm that has the best 'Time Complexity'.

And 'Time Complexity' can be defined as, the total time taken by an Algorithm to run.

How do we calculate the Time Complexity?

There are different scenarios of for calculation of time Complexity. Let us see the below :

Constant Operation

Say, you are given a task to add two numbers 5 and 3 and store the result in a variable.

Now, you can use any language(Java, C, C++) to do that. And the steps would be,

Define the first variable(Say x) and store 5 in it.

int x = 5;
Then, define the second variable(Say y) and store 3 in it.

int y = 3;
Next, we define the third variable(Say z) and store the added value in it.

int z = x + y;

Now, if we want to calculate the running time of the above add operation. There are three steps involved. And we can say that the running time is 3.

Also we can call it a 'Constant' operation.

Linear Operation

Now, let us look at the second scenario, where we are suppose to print the numbers from 1 to 10. And we need a loop in this case.

Let us take a 'while()' loop and print the numbers from 1 to 10. For the sake of understanding, we will just use the statement 'print' to print the numbers.

So, the steps would be,

Define a variable(Say i) and store the value '1' in it.

int i = 1;
Then we define the 'while(...)' loop and make the 'while(...)' loop run 10 times, printing the value of i at each iteration.
```
while(i <= 10) {
	
	print i;
	i = i + 1;
}
```
And the numbers from 1 to 10 would be printed on the screen.

Now, if we calculate the running time of the above program. We can see that there are two steps.

So, the first step,

int i = 1;

Is run once.

And the second step,

while(i <= 10) {
	
    print i;
    i = i + 1;
}

So, there are two statements inside the 'while(...)' loop.

print i;
i = i + 1;

And the 'while(...)' loop runs 10 times.

Now, since the 'while(...)' loop runs 10 times, the statements,

print i;
i = i + 1;

Will also run 10 times. And they will execute 20 times.

So, there will be 21 executions in total.

i.e. 1 time for the first step and 20 times for the second step.

Now, let us make the above time complexity a little simple.

So, in the above case, what we have seen is, the 'while(...)' loop runs 10 times. And there are two statements inside the 'while(...)' loop.

Now, to calculate the time complexity, all we can do is, ignore the statements inside the 'while(...)' loop. And consider, how many times the 'while(...)' loop runs.

So, the time complexity for the above program would be 10 and not 21.

Now, to make it a little simpler, let us rewrite the above code.

int n = 10;
int i = 1;
	
while(i <= n) {
	
	print i;
	i = i + 1;
}

We have created a variable 'n' and initialised it with 10.

int n = 10;

And put the variable 'n' in the 'while(...)' loop.

while(i <= n) {
	
    print i;
    i = i + 1;
}

So, the 'while(...)' loop runs 'n' times. Or 10 times, as the value of 'n' is 10.

And the time complexity would be 'n'.

This is called a 'Linear Time Complexity'.

Quadratic Operation

Next, let us look at the other scenario. Where we are suppose to print the numbers 1 to 5, 5 times.

Like the below pattern.

And if you are comfortable with programming, you know that we need nested loops to write the above sequence.

int n = 5;

int i = 1;
while(i <= n) {
    
    int j = 1;
    while(j <= n) {
        Print j;
        j = j + 1;
    }
        
    Print "\n"
    i = i + 1;
}

So, in the above code, we have initialised the value of 'n' with '5'.

int n = 5;

Now, there are two 'while(...)' loops.

int i = 1;
while(i <= n) {
		
    int j = 1;
    while(j <= n) {
        Print j;
        j = j + 1;
	}
		
	Print "\n"
	i = i + 1;
}

The inner 'while(...)' loop,

int j = 1;
while(j <= n) {
	Print j;
	j = j + 1;
}

Just prints each line,

1 2 3 4 5

And the outer loop,

int i = 1;
while(i <= n) {
		
	...
	while(j <= n) {
		...
		...
	}
		
	Print "\n"
	i = i + 1;
}

The outer loop makes the inner loop run 5 times so that all 5 lines are printed.

Now, let us look at the Time taken by the above program.

So, when the outer loop runs for the first time. The inner loop runs 5 times, printing the numbers from 1 to 5.

1 2 3 4 5

So, the total running time is 5.

Similarly, when the outer loop runs for the second time. The inner loop runs 5 times, printing the numbers from 1 to 5 in the second line.

1 2 3 4 5
1 2 3 4 5

And the total running time would be 5*2 = 10.

Same way, the outer loop runs third, fourth and fifth time printing all the 5 lines.

1 2 3 4 5  --------- 5 times
1 2 3 4 5  --------- 5 times
1 2 3 4 5  --------- 5 times
1 2 3 4 5  --------- 5 times
1 2 3 4 5  --------- 5 times

And as we can see each line runs 5 times.

So the total running time would be 5*5 = 25 times.

And as the value of 'n' is 5, we can also write the above running time as (n*n) or (n)² .

This is called 'Quadratic Time Complexity'.

There is also an important operation, i.e. Logarithmic Operation which we will be looking in a different lesson.

Next, let us look at the Space Complexity.

How do we calculate the Space Complexity?

The operations used in calculation of 'Space Complexity' is exactly same as the ones used in the calculation of 'Time Complexity'.

i.e. n, (n)² , log n and so on.

Let us take the above example to understand it.

Say we need to print all the numbers from 1 to 10.

int n = 10;
int i = 1;
            
while(i <= n) {
            
    print i;
    i = i + 1;
}

And as the name suggests, 'Space Complexity'. We are supposed to find the space taken by the above program.

Well! There are just two variables 'n' and 'i' for storing the data. And the 'Space Complexity' is Constant.

But there are also instances where we would be using arrays where the 'Space Complexity' could be n or log n or something else.

❮❮ PREV NEXT ❯❯