Calculate space complexity of algorithms


Calculate space complexity of algorithms

Space Complexity:

Space complexity is about the amount of memory space required by an algorithm during the execution of a program or an algorithm.

Space Complexity of Algorithm  S(n) is the number of units of memory used by an algorithm as a function of data size

for any algorithm, memory is required for the following purposes:

  • To store program instruction,

  • To store constant variable,

  • To store variable values,

  • And for a few other things like function calls, jumping statement, etc.


How to calculate space complexity of algorithms:

S(P)= C+Sp

S(P): Space Complexity

C: Fixed Part (independent or constant)

Sp: Variable Part (Dependent character)


Examples:

1) Algorithm abc(a,b,c)

{

return a+b+c*c(a+b)+4;

}

For every instance, 3 words are required  to store variable a, b, and c

S(P)= 3


2) Algorithm Sum(a[ ],n)

{

s=0;

for i=1 to n do

     s=s+a[i];

return s;

}

Here,

To store a[n] = n words

To store n = 1 word

Tp store s and i = 2 words

So the S(p)= n+3


Comments