What is Space complexity?
When we design an algorithm to solve a problem, it needs
some computer memory to complete its execution. For any algorithm,
memory is required for the following purposes...
- Memory required to store program instructions
- Memory required to store constant values
- Memory required to store variable values
- And for few other things
Space complexity of an algorithm can be defined as follows...
Total amount of computer memory required by an
algorithm to complete its execution is called as space complexity of
that algorithm
Generally, when a program is under execution it uses the computer memory for THREE reasons. They are as follows...
- Instruction Space: It is the amount of memory used to store compiled version of instructions.
- Environmental Stack: It is the amount of memory used to store information of partially executed functions at the time of function call.
- Data Space: It is the amount of memory used to store all the variables and constants.
NOTE
☀ When we want to perform analysis of an algorithm based on its Space
complexity, we consider only Data Space and ignore Instruction Space as
well as Environmental Stack.
That means we calculate only the memory required to store Variables, Constants, Structures, etc.,
That means we calculate only the memory required to store Variables, Constants, Structures, etc.,
To calculate the space complexity, we must know the
memory required to store different datatype values (according to the
compiler). For example, the C Programming Language compiler requires the
following...
- 2 bytes to store Integer value,
- 4 bytes to store Floating Point value,
- 1 byte to store Character value,
- 6 (OR) 8 bytes to store double value
Example 1
Consider the following piece of code...
int square(int a)
{
return a*a;
}
In above piece of code, it requires 2 bytes of memory to store variable 'a' and another 2 bytes of memory is used for return value.
That means, totally it requires 4 bytes of memory to complete its execution. And this 4 bytes of memory is fixed for any input value of 'a'. This space complexity is said to be Constant Space Complexity.
That means, totally it requires 4 bytes of memory to complete its execution. And this 4 bytes of memory is fixed for any input value of 'a'. This space complexity is said to be Constant Space Complexity.
If any algorithm requires a fixed amount of space
for all input values then that space complexity is said to be Constant
Space Complexity
Example 2
Consider the following piece of code...
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
In above piece of code it requires
'n*2' bytes of memory to store array variable 'a[]'
2 bytes of memory for integer parameter 'n'
4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each)
2 bytes of memory for return value.
That means, totally it requires '2n+8' bytes of memory to complete its execution. Here, the amount of memory depends on the input value of 'n'. This space complexity is said to be Linear Space Complexity.
'n*2' bytes of memory to store array variable 'a[]'
2 bytes of memory for integer parameter 'n'
4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each)
2 bytes of memory for return value.
That means, totally it requires '2n+8' bytes of memory to complete its execution. Here, the amount of memory depends on the input value of 'n'. This space complexity is said to be Linear Space Complexity.
If the amount of space required by an algorithm is
increased with the increase of input value, then that space complexity
is said to be Linear Space Complexity
