search
Log In
16 votes
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.
in Algorithms
edited by
867 views

2 Answers

19 votes
 
Best answer

Answer: C.

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 by
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 -

 ?

Answer:

Related questions

22 votes
3 answers
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)$.
asked Dec 5, 2015 in Algorithms makhdoom ghaya 1.3k views
4 votes
2 answers
2
316 views
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)$
asked Dec 8, 2015 in Algorithms makhdoom ghaya 316 views
26 votes
2 answers
3
1.5k views
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.
asked Dec 7, 2015 in Algorithms makhdoom ghaya 1.5k views
22 votes
5 answers
4
1.3k views
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$?
asked Dec 8, 2015 in Compiler Design makhdoom ghaya 1.3k views
...