1
$\begingroup$

The space complexity of the code snippet given below:

int *a = malloc(n * sizeof(int));
int sum=0;
for (i = 0; i < n; i++)
{
    scanf("%d", &a[i]);
    for (j = 0; j < n; j++)
    {
        int x = a[i];
        sum = sum + x;
    }
}
free(a);

This is question of a test. I answered it $O(n)$, considering space only for array and constant space for rest of the code. But in the answer they given $O(n^2)$ and there explanation is "The array is of size $n$ and the inner most loop we are declaring a variable $x$ every time the loop is executed, this loop is executed $O(n^2)$ time hence overall space complexity is $O(n^2)$." Now my doubt is what should be space complexity of

for (i = 1; i <= n; i++)
    int x = 10;

What i thought is that it should be $O(1)$ because in each iteration variable $x$ gets destroyed.

$\endgroup$
2
  • 2
    $\begingroup$ Your reasoning is correct. As you said, since $x$ is no longer needed, its space will be reused by $x$ from the next iteration. Most likely they'll probably literally occupy the same register or stack location, as it happens here: gcc.godbolt.org/z/3oq7qP . And it's not even a result of optimization. If they are not happy with this factual data, ask them for their rigorous definition of memory complexity and start discussion from there. $\endgroup$
    – user114966
    Aug 5 '20 at 20:36
  • $\begingroup$ For Turing Machines, memory complexity is easy to define: the length of the used part of the tape (i.e. the number of cells visited by the head). For C++ it's less clear, but the most natural is "the maximum amount of memory occupied at any moment". By this definition, your answer is correct: after you exit the body of the inner loop, $x$ doesn't occupy memory anymore. $\endgroup$
    – user114966
    Aug 5 '20 at 20:48
2
$\begingroup$

You are right. Are they saying if we run that loop n times then n different variables having name x will be created? This doesn't happen. Moreover, it is good practice to avoid unnecessary global variables. To check this yourself, you can try printing the logical address of x using this:-

for(i=0;i<10;i++)
   {
       int x=1;
       printf("%d\n",&x);
   }

The same logical address gets printed every time. So yes, the total space used by this is not dependent on n. It is O(1).

By the way, You could have thought that x gets destroyed only once at the end of last iteration and meanwhile all the values a[i] would be getting overwritten on the same x in each iteration. Even this is not what happens. x gets destroyed after each iteration and the space is made available for use by other parts.

$\endgroup$
1
  • $\begingroup$ Well, n variables named x are created. But n variables named x are also destroyed. So at any time, at most one exists. $\endgroup$
    – gnasher729
    Sep 18 '20 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.