CODEWITHSUNDEEP
calgorithmcomplexity-theory
Bunny Rabbit
Bunny Rabbit

Reputation: 8411

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)

Upvotes: 4

Views: 2663

Answers (4)

Saeed Amiri
Saeed Amiri

Reputation: 22555

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)

Upvotes: 10

Mateen Ulhaq
Mateen Ulhaq

Reputation: 27201

You could have been a bit more clearer... grumble grumble

<n = ?> : <return value> : <number of times called>
n = 0 : 1 : 1
n = 1 : 1 : 2
n = 2 : 2 : 4
n = 3 : 4 : 8
n = 4 : 8 : 16
n = 5 : 16 : 32
n = 6 : 32 : 64
n = 7 : 64 : 128
n = 8 : 128 : 256
n = 9 : 256 : 512
n = 10 : 512 : 1024

number_of_times_called = pow(2, n-1);

Let's try putting in inputs, shall we?

Using this code:

#include <iostream>

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


int main(int argc, char* argv[])
{
    for(int n = 0; 1; n++)
    {
       std::cout << "n = " << n << " : " << foo(n);
       std::cin.ignore();
 }

    return(0);
}

We get:

n = 0 : 1
n = 1 : 1
n = 2 : 2
n = 3 : 4
n = 4 : 8
n = 5 : 16
n = 6 : 32
n = 7 : 64
n = 8 : 128
n = 9 : 256
n = 10 : 512

Therefore, it can be simplified to:

double foo(int n)
{
    return((double)pow(2, n));
}

Upvotes: 1

Thomas Havlik
Thomas Havlik

Reputation: 1388

For one, it is poorly coded :)

double foo (int n) {         // foo return a double, and takes an integer parameter
    int i;                   // declare an integer variable i, that is used as a counter below
    double sum;              // this is the value that is returned
    if (n==0) return 1.0;    // if someone called foo(0), this function returns 1.0
    else { // if n != 0
        sum = 0.0;           // set sum to 0
        for (i =0; i<n; i++) // recursively call this function n times, then add it to the result
        sum +=foo(i);
        return sum;          // return the result
    }
}

You're calling foo() a total of something like n^n (where you round n down to the nearest integer)

e.g.:

foo(3)will be called 3^3 times.

Good luck, and merry Christmas.

EDIT: oops, just corrected something. Why does foo return a double? It will always return an integer, not a double.

Here would be a better version, with micro-optimizations! :D

int foo(int n)
{
    if(n==0) return 1;
    else{
        int sum = 0;
        for(int i = 0; i < n; ++i)
        sum += foo(i);
        return sum;
    }
}

Upvotes: 2

Wolph
Wolph

Reputation: 80031

The function is composed of multiple parts.

The first bit of complexity is the if(n==0)return 1.0;, since that only generates one run. That would be O(1).

The next part is the for(i=0; i<n; i++) loop. Since that loops from 0..n it is O(n)

Than there is the recursion, for every number in n you run the function again. And in that function again the loop, and the next function. And so on...

To figure out what it will be I recommend you add a global ounter inside of the loop so you can see how many times it is executed for a certain number.

Upvotes: 0

Related Questions