recategorized by
2,460 views
5 votes
5 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 time complexity of the above code is?

recategorized by

2 Answers

Best answer
11 votes
11 votes
Answer is $O(2^n)$

$T(n) = \displaystyle \sum_{i=0}^{n-1} T(i) + cn$

The last $cn$ is for the $n$ times the for loop is executing.

T(0) = 1
T(1) = 2
T(2) =  5
T(3) = 11
T(4) = 23
T(5) = 47

So,  $$T(n) = 2^n + 2^{n-1} - 1 = O(2^n)$$
selected by
0 votes
0 votes

With each addition to the input (n), the growth rate doubles, and the algorithm iterates across all subsets of the input elements. When an input unit is increased by one, the number of operations executed is doubled. O(2^n).

Related questions

9 votes
9 votes
2 answers
4
vineet.ildm asked Nov 7, 2016
5,807 views
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getti...