Click here to Skip to main content
14,425,302 members
Rate this:
Please Sign up or sign in to vote.
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
Comments
kavinderrana121 22-Oct-18 10:31am
   
@OriginalGriff Please help Sir
Rate this:
Please Sign up or sign in to vote.

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
Comments
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:
Please Sign up or sign in to vote.

Solution 2

Quote:
MY DOUBTS

Don't doubt, make sure.
Define a global variable, a counter,
chanje your code this way
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
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100