What is the complexity of this function c

Question

What is the complexity of the following function c?

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 complexity, can you help me figure out how to do this.

EDIT: This was an objective question asked at the exam, and the options provided were 1.o (1) 2.O (p) Ii (p!) 4.O (n ^ n)

Answer 1

It & Theta; (2 ^ n) (assuming f is the running time of the algorithm):

 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 constant operations, the exact time is 2 ⁿ .

Also in the case when you wrote this exam, both O (n!) And O (n ^ n) are true, and the closest answer to & Theta; (2 ^ n) among them is O (n!), But if I were a student, I would mark both of them :)

---

Explanation for 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) 

Answer 2

Firstly, it is poorly encoded :)

 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 call foo () as a whole, something like n ^ n (where you round n to the nearest integer)

eg:.

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

Good luck and merry christmas.

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

Here would be the best version with micro-optimization !: 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; } } 

Answer 3

You might be a little 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 to insert the inputs, right?

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:

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

Answer 4

The function consists of several parts.

The first bit of complexity is if(n==0)return 1.0; since it only generates one run. This will be O(1) .

The next part is a for(i=0; i<n; i++) loop for(i=0; i<n; i++) . Since this comes from 0..n , this is O(n)

Than recursion, for each number in n you run this function again. And in this function again the cycle and the next function. And so on...

To find out what I will recommend, you add a global perch inside the loop so you can see how many times it runs for a certain number.