Space
complexity
Hey
people in this blog you are going to read about “Space Complexity”.
We know that after hearing this term, space complexity, you would
go through its definition.
According
to WIKI , " The space complexity of an algorithm or a computer program is the amount of memory space required to solve an
instance of the computational
problem as a function of
characteristics of the input. It is the memory required by an algorithm to
execute a program and produce output.”
Space complexity is the
amount of memory used by the algorithm (including the input values to the
algorithm) to execute and produce the result, i.e. Space complexity = Auxiliary Space + input space.
You might me wondering what auxiliary space is. Isn’t it same as space complexity? Because beginners
even few good coders make this mistake.
Auxiliary
Space is the extra space or the temporary space used by the algorithm during
its execution.
Ever wondered "Why is it important to estimate the
space complexity of an algorithm?"
One
reason that it is important to estimate the space complexity of an algorithm,
the space it needs relative to inputs, is that some algorithms are designed
with particular limitations. Some are designed with a cap on total storage
space use, which can result in rough or imprecise results. Others are made to
enforce precise results regardless of the space used.
Calculating the space complexity:
|
TYPE |
SIZE |
|
bool, char,
unsigned char, signed char, __int8 |
1byte |
|
__int16,
short, unsigned short, wchar_t, __wchar_t |
2bytes |
|
float,
__int32, int, unsigned int, long, unsigned long |
4bytes |
|
double,
__int64, long double, long long |
8bytes |
Look at the code below,
Above, variables x, y, u and z are all integer type. So, each will take 4 bytes each. So, total memory requirement will be 4*4 + 4 = 20 bytes. The extra 4 is for the return value.
As the space requirement is fixed. We call this Constant space complexity.
Look at another code,
Ø Above, 4*n bytes of space is required for the array b[] elements. And, 4 bytes for each variable x, i, m. Therefore, total memory requirement is 4n+12.
This
is increasing linearly with increasing value of n. This is called as linear space complexity.
Similarly we have quadratic and other space complexities as well.
We have also covered Asymptotic Analysis which is very important for understanding the time complexity of an algorihtm, check it out by clicking here.
