Chapter 2: Performance analysis of an algorithm: Space Complexity

In this chapter we shall look at:

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:

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

and other factors will also come in to consideration.

In this chapter we shall look at space complexity.

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

1. Fixed or constant space complexity

2. Linear 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.

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

For example:

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).

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”.