What is Space Complexity

Space Complexity

The amount of memory used by the
algorithm to execute it completely and produce the result is known as space
complexity.

To execute an algorithm it must be loaded into the
main memory. The memory can be used in different forms:


 
Variables (This includes the constant values
     and temporary values)
 
Program Instruction
 
Execution


 

Auxiliary Space

The extra space or temporary space used by the
algorithms during its execution is known as auxiliary space.

Space Complexity = Auxiliary
Space + Input space

Now let's learn how to compute space complexity by
taking a few examples:

 

Example 1:  

int w = x + y + z;

return(w);           
                     
    

In the above expression,
variables x, y, z, and w are all integer types, hence
they will take up 4 bytes each (depending on the compiler),

So total memory requirement will be  (4
variables (each of size 4) + 4 (return value (auxiliary space))) = 20 bytes.

And because this space requirement is fixed for the
above example, hence it is called Constant Space Complexity i.e.
O(1).

 

 Example 2:

// n is the length of array a[]

int sum(int a[], int n)

{

         
int x = 0;

         
for(int i = 0; i < n; i++)

         
{       

         
    x  = x +
a[i];               

         
}

         
return(x);

}


 
In the above code, 4*n bytes of
     space is required for the array a[] elements.
 
4 bytes each for x, n, i, and
     the return value.


Hence the total memory requirement will be (4n
+ 3(variables) * 4(byte each variable)), which is increasing linearly with the increase
in the input value n, hence it is called Linear Space Complexity
i.e. O(n)

 

Example 3:

#include<stdio.h>

int main()

{

  int a = 12, b = 15, c=10,z;

  z = a + b+c;

  printf("%d", z);

}

Explanation:

In the above program, 4 integer
variables are used. The size of the integer data type is 2 or 4 bytes (which
depends on the compiler).

Now, let’s assume the size is 4
bytes.

So, the total space occupied by the
above-given program is 4 * 4 = 16 bytes. Since no additional variables are
used, no extra space is required.

Hence, space complexity for the above-given
program is O(1), or constant.

 

Example 4:

#include <stdio.h>

int main()

{

  int n, i, sum = 0;

  scanf("%d", &n);

  int arr[n];

  for(i = 0; i < n; i++)

  {

    scanf("%d",
&arr[i]);

    sum = sum + arr[i];

  }

  printf("%d", sum);

}

Explanation:

In the above-given code, the array consists of n
integer elements. So, the space occupied by the array is 4 * n.

Also, we have integer variables such as n, i, and
sum. Assuming 4 bytes for each variable, the total space occupied by the
program is 4n + 12 bytes.

Since the highest order of n in the equation 4n +
12 is n, so the space complexity is O(n) or linear.

 

Example 5:

Factorial of a number (Iterative Method)

int fact=1;

for(int i=1; i<=n; i++)

{

fact=fact*i;

}

return fact;

Explanation:

In the above program, 3 integer variables are used.
The size of the integer data type is 2 or 4 bytes (which depends on the
compiler).

Now, let’s assume the size is 4 bytes.

So, the total space occupied by the above-given
program is 3 * 4 = 12 bytes (i.e. fact=4bytes, i=4bytes, n=4bytes). Since no
additional variables are used, no extra space is required (or let us assume
auxiliary space is 4 bytes which is constant).

Space =12bytes+4bytes=16 bytes

Hence, space complexity for the above-given
program is O(1), or constant.

 

Example 6:

Factorial of a number (Recursive Method)

int fact(n)

{

if(n<=1)

{

          return 1;

}

else

{

         
return(n*fact(n-1));

}

}

Explanation:

Let us assume n=3


 

  

  
1
  
 
 

  

  
   2*fact(1)
  
 
 

  

  
 3*fact(2)
  
 


     stack

Hence, space complexity for the above-given
program is O(n), or linear time.