GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
1.5k views
double foo(int n)
{
    int i;
    double sum;
    if(n == 0)
    {
        return 1.0;
    }
    else
    {
        sum = 0.0;
        for(i = 0; i < n; i++)
        {
            sum += foo(i);
        }
        return sum;
    }

}

The space complexity of the above code is?

  1. $O(1)$
  2. $O(n)$
  3. $O(n!)$
  4. $n^n$
asked in Programming by Veteran (59.8k points)  
recategorized by | 1.5k views
Sir but how we get O(n) recursion depth every time we call a foo(i) it again call foo(i) from (0 to n).

Sir plz explain this question furthur more.
recursion depth- this counts only the function calls that are active at a time- for(i = 0 to n), here before f(i) is called f(i-1) would be returned back-so this won't increase the recursion depth.
got it sir where i was wrong.. thanku

1 Answer

+19 votes
Best answer

A. The code here is storing only local variables. So, the space complexity will be the recursion depth- maximum happening for the last iteration of the for loop- foo(n-1) - foo(n-2) - ....  - foo(0) all live giving space complexity O(n).

B. To store the n values we need space complexity O(n). So, the space complexity won't change and will be O(n).

answered by Veteran (288k points)  
edited by
@Arjun sir what will be the time complexity of (B)

Will be O(n)?

because all value stores when it computed. So, only time for for loop execution ,i.e.O(n)

and for summation from 1 to n i.e. O(1)

and for question (A) time complexity will be O(n!), because of n time function call

Am I right?
B would be O(n) but you can check A again writing a recurrence formula. It should be polynomial..

@Arjun Sir will this be recurrence relation for time complexity of the function.

@Arjun sir, time complexity for A will be $O(2^n)$ and for B will be $O(n)$, right ?
sir,answer of B should be O(1).Here we are storing values of function foo when it is computed once.So all time only maximum 3 activation records present in the recursion stack.ex,suppose foo(4) is called from main.So,foo(4) will be pushed in the stack.then foo(0),which will be returned.So.present content of the stack is foo(4).Now foo(1) will be pushed,which will push foo(0).So,present content is foo(4)foo(1)foo(0),ie 3 activation records.Now,foo(0),foo(1) will be popped one by one.Now there is foo(4).Then foo(2) will be pushed,which will then push(0) and it will be returned immediately,then foo(1) and it will also be returned,because it's value is already stored.So conten of the stack was foo(4)foo(2)foo(0) and after that foo(4)foo(2)foo(1).Now,foo(2) will be returned.Now,foo(3) will be called,ie.foo(3)will be pushed,which will push foo(0),returned,then foo(1),will be returned,then foo(2)and it will be returned,as value of it is already stored.So here stack contents would be foo(4)foo(3)foo(0) then foo(4)foo(3)foo(1) then foo(4)foo(3)foo(2).So,any value of n,always maximum 3 activation records present in the stack.So,here space complexity should be O(1).
Still we need to store $n$ unique values from $1-n$.

Why are you worrying about activation records?

"stores the value of foo(i) 0 <= i < n"

This requires an array of size n rt? And only that is required to answer the question.

Arjun sir the time complexity of A part will be O (2^n)?? Can u plz check?
@arjun sir , space complexity is $O(n)$ But What is Time complexity ?

Here for each value of i recursive function is called and again it get looped .  So wont the time complexity will be $O(n^{n}) $ ?
Time: n power n is right


Top Users Jul 2017
  1. Bikram

    4386 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1850 Points

  4. joshi_nitish

    1686 Points

  5. Arjun

    1340 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1112 Points

  8. Shubhanshu

    1080 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    732 Points


24,031 questions
30,983 answers
70,430 comments
29,358 users