The definition of Space Complexity is : Total amount of computer memory ( or you can say memory space ) require to solve that given problem of particular size.
In simple terms space complexity is defined as Number of steps a program takes for input of size n .
We calculate space complexity by addition of two components.
space complexity = Fixed component + variable component
Fixed component = size of variable, constants
Variable component = size of input and output
Now, for this problem :
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
Here fixed part is i , sum , array A[] . And variable part is input n .
now see, for() loop for array A[] is running up to n inputs ( from i=0 to n inside the array A[]) so to store them we need n space , that means array A[] takes n space.
sum takes 1 space, variable i takes 1 space.
Input n takes 1 word space.
hence total space required = n+1+1+1 = n+3
so space complexity of this problem is O(n)
Sometimes we say only auxiliary space meaning the extra space in addition to the input and then the answer here will be $O(1)$.
Where to read this topic ?
Reference :
- https://www.cs.northwestern.edu/academics/courses/311/html/space-complexity.html
- http://letslearncs.com/time-and-space-complexity/
- https://www.quora.com/How-do-we-calculate-space-time-complexity-of-an-algorithm