GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
1.1k 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 (58.2k points)   | 1.1k 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

+14 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 (280k 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 (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}) $ ?
Answer:

Related questions

Top Users Feb 2017
  1. Arjun

    5396 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,023 answers
59,698 comments
22,136 users