Space Complexity of Iterative Algorithms

For Complete YouTube Video: Click Here

In this class, we will try to understand the Space Complexity of Iterative Algorithms.

We have already discussed how to find the Time Complexity of Algorithms in our previous classes.

Table of Contents

The Space Complexity of an algorithm is the Auxiliary and Input Space required by an algorithm to complete its execution.

Auxiliary Space is the extra space or temporary space used by an algorithm.

Input Space is the Input Space provided to the algorithms.

We will consider the two example algorithms shown below for a better understanding.

In the first algorithm, we have only Auxiliary space used by the algorithm, but it doesn’t have Input Space.

The temporary space used by the algorithm is the space for variables i, j and sum.

If we assume that the space used by a variable is a unit of space, then the algorithm uses three units of space.

Therefore the amount of space used by algorithm 1 is constant.

The space complexity of the algorithm is O(1).

Similarly, Algorithm 2 use both the Auxiliary and Input Space.

In Algorithm 2, the input space is n.

The Auxiliary Space is for n, i, sum.

The Space Complexity of algorithm 2 is

S = n + 1 + 1 + 1

= n + 3

O(n)