Space complexity | Linear Space Complexity | Examples | Coding Winds | We care about the future of future

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. 

If you still have any doubt on this topic then do come to us via email "sophomoretechs@gmail.com" or via instagram "@coding.winds".

We also have something on "Dynamic Memory Allocation in C/C++", check it out by clicking here.