The Gateway to Computer Science Excellence
+14 votes
450 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 by Boss (30.8k points)
edited by | 450 views

2 Answers

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

by Active (3.5k points)
edited by
0 votes

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 -

 ?

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
198,341 comments
105,032 users