452 views

Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$.

int f (int n)
{
if (n==0 || n==1)
return 1;
else
return f (n - 1) + f(n - 2);
}

Assuming a typical implementation of the language, what is the running time of this algorithm and how does it compare to the optimal running time for this problem?

1. This algorithm runs in polynomial time in $n$ but the optimal running time is exponential in $n$.
2. This algorithm runs in exponential time in $n$ and the optimal running time is exponential in $n$.
3. This algorithm runs in exponential time in $n$ but the optimal running time is polynomial in $n$.
4. This algorithm runs in polynomial time in $n$ and the optimal running time is polynomial in $n$.
5. The algorithm does not terminate.

edited | 452 views

It is fibanacci series generation. it takes exponential time if we won't use dynamic programming.

If we use dynamic programming then it takes $O(n)$

by Active (3.5k points)
edited
0

this is fibonacii program which can can be optimises to O(logn) using Divide and conquer technique

https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

T(n)=T(n-1)+T(n-2)+1

For simplicity, we can write like this...

T(n)=2T(n-1)+1

a=2, b=1, k=0

According to Muster's theorem

T(n)= O($n^{k}a^{\frac{n}{b}}$) = O($2^{n}$)

For more about muster theorem- https://www.geeksforgeeks.org/master-theorem-subtract-conquer-recurrences/

The above problem can also be solved using the dynamic approach, in which we don't have to compute T(n-1) two times in the given recurrence relation. We can compute for the 1st time and store it for the next. In this way time complexity would be...

T(n) = T(n-1)+1

a=1, b=1, k=0

According to Muster's theorem

T(n)= O($n^{k+1}$) = O($n^{1}$)

So C is the right answer.

by Active (4.3k points)
0

@Nitesh Singh 2

How did you wrote this -

?