recategorized by
18,926 views
53 votes
53 votes
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$
recategorized by

5 Answers

Best answer
64 votes
64 votes

  1. 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)$.
     
  2. To store the $n$ values we need space complexity $O(n)$. So, the space complexity won't change and will be $O(n)$.

Correct Answer: $B$

edited by
1 votes
1 votes
Example for foo(5) ,when foo(4) is called in loop ,
 it will have highest Depth
For foo(4), foo(3) will have Highest depth.
for foo(3) ,foo(2) will have highest depth.
for foo(2),foo(1) has highest depth.

foo(1) just execute loop 1 time and call foo(0).
So height of foo(2) is 3.
So height of foo(3) is 4.
height of foo(4) is 5.
height of foo(5) is 6.

For foo(n) we occupy approx n+1 lvls in tree
and so n+1 stack records and each record has space complexity of O(1)
as no extra space is used.

So overall Space complexity = Height of tree x Space complexity of each lvl
=O(n x 1)
=O(n)
1 votes
1 votes

Time complexity will be O($2^{n}$) if n= 2 total recursive calls are 4 i.e (2^2) therefore for n , total recursive calls will be (2^n) 

Answer:

Related questions

1 votes
1 votes
1 answer
3
1 votes
1 votes
1 answer
4
A_i_$_h asked Jul 24, 2017
390 views
A binary search algorithm is implemented using recurrsionthen what is the space and time complexity?