Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the complexity of this c function

what is the complexity of the following c Function ?

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;
    }
}

Please don't just post the complexity can you help me in understanding how to go about it .

EDIT: It was an objective question asked in an exam and the Options provided were 1.O(1) 2.O(n) 3.O(n!) 4.O(n^n)

like image 461
Bunny Rabbit Avatar asked Dec 13 '22 17:12

Bunny Rabbit


1 Answers

It's Θ(2^n) ( by assuming f is a running time of algorithm we have):

f(n) = f(n-1) + f(n-2) + ... + 1
f(n-1) = f(n-2) + f(n-3) + ...
==> f(n) = 2*f(n-1), f(0) = 1
==> f(n) is in O(2^n)

Actually if we ignore the constant operations, the exact running time is 2n.

Also in the case you wrote this is an exam, both O(n!) and O(n^n) are true and nearest answer to Θ(2^n) among them is O(n!), but if I was student, I'll mark both of them :)


Explanation on O(n!):

for all n >= 1: n! = n(n-1)...*2*1 >= 2*2*2*...*2 = 2^(n-1) ==>
2 * n! >= 2^n ==> 2^n is in O(n!),
Also n! <= n^n for all n >= 1 so n! is in O(n^n)

So O(n!) in your question is nearest acceptable bound to Theta(2^n)
like image 141
Saeed Amiri Avatar answered Jan 02 '23 23:01

Saeed Amiri