edited by
3,515 views
4 votes
4 votes
int sum(int A[], int n)
{
   int sum = 0, i;
   for(i = 0; i < n; i++)
      sum = sum + A[i];
   return sum;
}
edited by

2 Answers

Best answer
3 votes
3 votes

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 :

  1. https://www.cs.northwestern.edu/academics/courses/311/html/space-complexity.html
  2. http://letslearncs.com/time-and-space-complexity/
  3. https://www.quora.com/How-do-we-calculate-space-time-complexity-of-an-algorithm
selected by
Answer:

Related questions

2 votes
2 votes
3 answers
4
Laahithyaa VS asked Sep 9, 2023
892 views
. What will be the value returned by the following function, when it is called with 11?recur (int num){if ((num / 2)! = 0 ) return (recur (num/2) *10+num%2);else return 1...