TIFR CSE 2015 | Part B | Question: 3

Question

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?

• A. This algorithm runs in polynomial time in $n$ but the optimal running time is exponential in $n$.
• B. This algorithm runs in exponential time in $n$ and the optimal running time is exponential in $n$.
• C. This algorithm runs in exponential time in $n$ but the optimal running time is polynomial in $n$.
• D. This algorithm runs in polynomial time in $n$ and the optimal running time is polynomial in $n$.
• E. The algorithm does not terminate.

Answer 1

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

Comments

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

Refhttps://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0ahUKEwjFkoy11YXbAhWKgI8KHfmkALYQFgg0MAE&url=http%3A%2F%2Fwww.facweb.iitkgp.ernet.in%2F~sourav%2FLecture-03.pdf&usg=AOvVaw3L6QCvjHruwKHoa6yxpFpR

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

Although answer will be C

Answer 2

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.

Comments

@Nitesh Singh 2

How did you wrote this -

 ?

---

@ayushsomani

For worst case T(n),

T(n-2) which is less than T(n-1)

if we consider T(n-2) approximately equal to T(n-1), its just we are adding some time in T(n-2) to make it upto T(n-1) in worst case.

then we can write T(n-1) + T(n-2) = 2T(n-1)