Click here to Skip to main content
15,896,330 members

Is the space complexity of below program is correct?

kavinderrana121 asked:

Open original thread
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
Tags: C, Algorithms, Analysis

Plain Text
ASM
ASP
ASP.NET
BASIC
BAT
C#
C++
COBOL
CoffeeScript
CSS
Dart
dbase
F#
FORTRAN
HTML
Java
Javascript
Kotlin
Lua
MIDL
MSIL
ObjectiveC
Pascal
PERL
PHP
PowerShell
Python
Razor
Ruby
Scala
Shell
SLN
SQL
Swift
T4
Terminal
TypeScript
VB
VBScript
XML
YAML

Preview



When answering a question please:
  1. Read the question carefully.
  2. Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
  3. 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.
  4. 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.
Please note that all posts will be submitted under the http://www.codeproject.com/info/cpol10.aspx.



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900