GATE2005-81a

Question

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?

• A. $O(1)$
• B. $O(n)$
• C. $O(n!)$
• D. $n^n$

Comments

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

---

Having same doubt! Thanks for clearing concept! :)

Answer 1

• 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)$.

Comments

@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}) $ ?

---

In this code , Time complexity is O(2ⁿ) ,

it depends upon total number of function calls at each level ..

It is like :

like level 0 : 1 function call 

like level 1 : 2 function calls 

like level 2 : 4 function calls 

like level 3 : 8 function calls 

....... and so on 

so it would be O(2ⁿ)

---

i think Time complexity will be O(2^n)

---

Space Complexity:   O(n)  //Height of stack will never exceed n.


Time complexity:    

foo(0) = 1                                  //one function call

foo(1) = 0+  foo(0)                    //needs two function calls  foo(1) & foo(0)
foo(2) = 0 + foo(0) + foo(1)     //needs 4 function calls ..  one foo(2), foo(1) takes two calls, foo(0) takes one 

foo(3) = 0 + foo(0) + foo(1) + foo(2)     //needs 9....  1+1+2+4= 8

foo(4)=0 + foo(0) + foo(1) + foo(2) +foo(3)    // needs 16 function calls....  1+1+2+4+8 = 16 calls

So when n=4 nearly 16 calls.... when n=3 nearly 8 calls...
Number of function calls  clearly  O(2^n)
@Bikram sir

---

@Ahwan

I think instead of counting additions we need to count function calls. There are many type time complexity we can calculate, depends upon the operation we choose. Like if the function contain multiply operation too we could calculate TC(mutiply), similarly although you have calculated answer correctly which is O(2^n), the base choosen in not correct,TC(addition) is less, like for foo(4) there are 15 additions not 16.

 

But if you calculate according to no. Of function calls there are 16 such calls. Hence TC is O(2^n).

---

@bhuv you are right. I replaced it to function calls.

---

No it will be O(n^(n))

---

Doubt

Sir, why in the recursion tree at level 0 nodes from 0 to n but for loop is going from 0 to n-1

---

What will be recurrence relation for time complexity ??

---

@jatin khachane 1, If you observe, every time function calls are becoming twice.

which approximate to reccurence relation,

T(n) = 2T(n-1) + 1

=> T(n) = O(2^n)

Answer 2

Requires N units for a plus extra space for n, i and sum, so it's O(N)