Is the space complexity of below program is correct?

Question

0.00/5 (No votes)

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 22-Oct-18 4:28am

kavinderrana121

Updated 22-Oct-18 8:42am

Add a Solution

Comments

kavinderrana121 22-Oct-18 10:31am

@OriginalGriff Please help Sir

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

CPallini · Answer 1 · 2018-10-22T07:09:00

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)

Posted 22-Oct-18 7:09am

CPallini

Updated 22-Oct-18 8:24am

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).

Patrice T · Answer 2 · 2018-10-22T08:43:00

Quote:
MY DOUBTS

Don't doubt, make sure.
Define a global variable, a counter,
chanje your code this way

C++

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

C++

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