GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
1.2k 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.9k points)   | 1.2k 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

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

Related questions



Top Users May 2017
  1. akash.dinkar12

    3338 Points

  2. pawan kumarln

    2066 Points

  3. Bikram

    1922 Points

  4. sh!va

    1672 Points

  5. Arjun

    1614 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1174 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1018 Points

  10. Arunav Khare

    758 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    692 Points

  3. Arnab Bhadra

    632 Points

  4. Arjun

    342 Points

  5. bharti

    328 Points


22,888 questions
29,193 answers
65,292 comments
27,691 users