Space Complexity

Any solution to a problem requires memory to complete its required task. For any algorithm, memory is used for the following entities:

• Variables be it temporary or constant.
• The instruction of the program.
• Memory is required for the execution that is for binary.

Space complexity is the amount of space/memory required by the algorithm to execute and produce the result.

while executing, algorithm uses memory for three reasons:

• Instruction space: It is the amount of space/memory required to save the compiled version of the instruction.
  
• Environmental Stack: This is used during the function call. If an algorithm has a function which again calls a new function, then the context (variables) of the old function is stored in the system stack and is restored once the called function returns.
  
  For example, if a function A() calls function B() inside it, then all the variables of the function A() will get stored on the system stack temporarily, while the function B() is called and executed inside the function A().
  
• Data Space: It is the amount of space required by variables and constant.

But while computing the pace complexity of an algorithm, we would consider only Data space and neglect the Intruction and Environmental Space.

Calculating the Space Complexity:

To calculate the space complexity, we need to know the amount of memory required by each different type of datatype variables. This varies depending upon the type of operating system but the method to calculate the system complexity remains the same.

Type	Size
bool, char, unsigned char, signed char	1 bytes
short , unsigned short	2 bytes
int, unsigned int	2 or 4 bytes
long	8 bytes or 4 bytes for 32 bit OS
unsigned long, double, long double	8 bytes

We will be seeing a few examples to understand the space complexity.

Example-1:

int fun()
{
    int d = a + b + c;
    return d;
}

In the above example, variables a, b, c, d are of integer type, hence they would be occupying 4 bytes each. The total memory required would be 16 bytes + 4 bytes for the return, making it 20 bytes.

The space required is fixed for the above example, hence it is called Constant space complexity.

int sum ( int arr[], int n)
{
  int result = 0;
  for ( int i =0; i < n; i ++)
       result = result + arr[i];
  return result;
}

Example-2:

In the above example, since it is an integer array and the size of the array is ‘n’, hence the total space occupied by array will be (n *4) bytes.

The other variables like ‘result’, ‘n’ and ‘i’ would be taking 4 bytes each. The total space would be 4n + 12. Thus, the space occupied by this algorithm is directly proportional to the size of the array that is linearly dependent on array size. Hence, space complexity is known as linear space complexity.

Note:
In today’s world where space is not a big concern, time complexity is given more importance. But in embedded project where the space is a bit concern, the algorithm with the least space requirement should be chosen.

Relevant article:

• Introduction: Data structure and algorithm
• Algorithmic Analysis
• Time Complexity
• Asymptotic Notation

---

‹ Time Complexity

Asymptotic Notation ›

---

Categories: Data Structure and Algorithm