14,425,302 members
Rate this:
See more:
I have to calculate space complexity for this function if we see according to stack size then it will be O(n) but in every recursive call two arrays are consuming extra space that is 2n or of order O(n)

MY DOUBTS

1)When we calculate time complexity for this function the process will be as follows as in every recursive call O(n) extra space is taken by two arrays(I am taking only order of 2n ) and since stack size is O(n) then space complexity is O(n^2)

2) what will happen if i replace these two arrays with a 2d array then in every recursive call O(n^2) extra space will be taken and since stack size is O(n) then space complexity this time will be O(n^3)

NOTE Nothing special about this function only calculating space complexity leave the garbage value since i am not freeing the memory after recursion

What I have tried:

```testfun(n){
if(n==0)
return;

int *a=malloc(sizeof(int)*n);
int *b=malloc(sizeof(int)*n);
for(int i=0;i<n;i++)
{  a[i]=n+2*i;
b[i]=n+3*i;
}

testfun(n-1);
free(a);
free(b);

}```

NOTE I am clearing memory after recursion
Posted
Updated 22-Oct-18 9:42am
kavinderrana121 22-Oct-18 10:31am

Rate this:

## Solution 1

With such a function, when `N` grows, you can safely ignore the space taken by stack allocation.
On the heap, due to the recursive calls you have
`memory(N) = 2*N + .. + 4 + 2`
that is
`memory(N) = 2*N!`
(measured in `sizeof(int)`, of course).
So the function space complexity is
```O(N!)
```

Sorry I made a blunder (many thanks to Patrice T for spotting it). I actually multiplied what I have to add instead.
So
`memory(N) = N(N+1)`

And function space complexity is
`O(N^2)`
v2
Patrice T 22-Oct-18 14:09pm

Are you sure about the '!' ?
CPallini 22-Oct-18 14:16pm

OOPS. You are right I made a blunder (multiplication instead of addition) I am going to amend it.
Thank you very much for pointing it out.
(I do hope is correct, now).
Rate this:

## Solution 2

Quote:
MY DOUBTS

Don't doubt, make sure.
Define a global variable, a counter,
```testfun(n){
if(n==0)
return;

int *a=malloc(sizeof(int)*n);
counter += n;
int *b=malloc(sizeof(int)*n);
counter += n;
for(int i=0;i<n;i++)
{  a[i]=n+2*i;
b[i]=n+3*i;
}

testfun(n-1);
free(a);
free(b);

}```

then, change function call to
```counter = 0;
testfun(n);
// at this point, counter contain the total memory allocated to arrays over recursion```