# TIFR2015-B-3

867 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

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)$

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/

1 vote

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.

0

@Nitesh Singh 2

How did you wrote this -

?

## Related questions

1
1.3k views
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ is $O(\log n. \log \log n)$ but not $O(\log n)$. $T(n)$ is ... $O(\log^{2} n)$ but not $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n. \log \log n)$ but not $O(\log^{2} n)$.
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ if and only $( \pi (u), \pi (v)) \in E_{2}$. Consider the ... (ii) $L$ is $NP$- hard. (iii) $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$
Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning ... minimum spanning tree here. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.
Consider the following grammar (the start symbol is $E$) for generating expressions. $E \rightarrow T - E \mid T + E \mid T$ $T \rightarrow T * F \mid F$ $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$ With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?