GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
908 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 Algorithms by Veteran (56k points)   | 908 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

+13 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 (272k points)  
selected 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 (n^2)?? 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}) $ ?
Top Users Jan 2017
  1. Debashish Deka

    7172 Points

  2. Habibkhan

    4696 Points

  3. Vijay Thakur

    4308 Points

  4. sudsho

    4090 Points

  5. saurabh rai

    4024 Points

  6. Arjun

    3292 Points

  7. santhoshdevulapally

    3066 Points

  8. GateSet

    3016 Points

  9. Bikram

    3014 Points

  10. Sushant Gokhale

    2892 Points

Monthly Topper: Rs. 500 gift card

18,838 questions
23,808 answers
51,589 comments
20,148 users