In this chapter we shall look at:

### 2.1 Why we need to calculate the performance of an algorithm?

2.2 What is space complexity?

2.3 Classification of space complexity

2.3.1 Fixed or constant space complexity

2.3.2 Linear space complexity

## 2.1 Before we go to space complexity, let us understand why we need to calculate the performance of an algorithm?

Consider 2 programmers “A” and “B”. Both of them submits 2 different solutions for the same program. Now how do we decide which solution is efficient and performs better?

And also A’s program might perform better for small number of input but will not perform when the input size increases.

Similarly, B’s program will not perform when the input size is small but will perform better for large number of input.

Hence to determine which of the solution is better, we take a look at 2 important factors that decide the performance of an algorithm:

1. Time complexity

2. Space Complexity

If you are developing a web based application, additional factors like:

3. Bandwidth usage

4. Number of simultaneous connections

and other factors will also come in to consideration.

In this chapter we shall look at space complexity.

## 2.2 What is space complexity?

Space complexity is about calculating the amount of space consumed by algorithm during the course of its execution.

## 2.3 Space complexity can be broadly classified into 2 types.

1. Fixed or constant space complexity

2. Linear space complexity

### 2.3.1 Fixed or constant space complexity

In this method, the size of space consumed will not be increased with the increase of input size.

For example:

Find the square of a number:

Pseudo code:

int getSquare (int n) { return (n * n) }

Here we can solve the problem without consuming any extra space, hence the space complexity is constant even if the input size increases.

### 2.3.2. Linear space complexity

Here the space consumed will be increased with the increase of input size.:

### Example 1. Calculate the sum of “n” numbers given in the array.

Pseudo code:

int calculate_sum(int arr[], int length) { int total_sum = 0; int i = 0; for( i= 0; i< len; i++) { total_sum = total_sum + arr[i]; } }

From the above code, we can see that:

A variable “**total_sum**” that takes constant sum of 1 unit

A variable “**length**” that takes constant sum of 1 unit

A variable “**i**” that takes constant sum of 1 unit

But the variable **arr[]** is an array, it’s space consumption **increases with the increase of input size**. i.e n.

Hence the space consumption is [3 + n] units.

As we can see in further chapters, we are interested in the performance of the algorithm, for a greater value of “n”. Hence we can ignore the constants, and come to a conclusion that the total space complexity of the above algorithm is O(n).

**Example 2: Let us calculate space complexity for matrix multiplication.**

Pseudo code:

int add_matrix( int a[m] [n], int b [m] [n], int m, int n) { for (i = 0; i< n; i++) { for(j = 0; j<n; j++) { c[i][j] = a[i][j] * b[i][j] } } }

From the above code, we can see that:

A variable “m” that takes constant sum of 1 unit

A variable “n” that takes constant sum of 1 unit

A variable “i” that takes constant sum of 1 unit

A variable “j” that takes constant sum of 1 unit

But we have 3 matrix variables of size arr[m][n] space consumption increases with the increase of input size. For one matrix will consume “**n^2**” space, for 3 it will consume “3*n^2” space.

Hence total space consumed is “4 + 3n^2”.

For larger size of input we ignore the constants, hence the space consumed is “**n^2**”.

So in this chapter we saw an introduction to why we need time and space complexity and learnt about space complexity in detail.

In the next chapter we shall learn about Time Complexity. This is an important topic.

AJ’s guide for DS and Algorithms..Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

## donReddy

Nice tutorial sir.