2,769 views
0 votes
0 votes

Consider the following code segment to find the $n^{th}$ Fibonacci number:

Fib(n)
{
   if(n==0) {return 0;}
 
   if(n==1) {return 1;}
   
   else { return(Fib(n-1) + Fib(n-2)); }
}


The time complexity of the above code and time complexity of the same problem solved using dynamic programming is______
$A)O(n^{2}),O(n)$
$B)O(2^{n}),O(n)$
$C)O(2^{n}),O(n^{2})$
$D)$None of the above 

2 Answers

0 votes
0 votes

first part is easy we can solve recurrence relation t(n)=t(n-1)+t(n-2)+c=0(2$^{n}$)

for second part we can make a programm like this

public static int fibonacciLoop(int nthNumber) {
        //use loop
        int previouspreviousNumber, previousNumber = 0, currentNumber = 1;

        for (int i = 1; i < nthNumber ; i++) {

            previouspreviousNumber = previousNumber;

            previousNumber = currentNumber;

            currentNumber = previouspreviousNumber + previousNumber;

        }
        return currentNumber;
    }

time complexity=0(n).

reference=https://dev.to/khalilsaboor/fibonacci-recursion-vs-iteration--474l

0 votes
0 votes
option B) is correct answer,  Without DP – O(2^n) , using masters theorem

Using DP – every time time result is calculated store it in an array, if result is already computed then there is no need to compute it again. Therefore in worst case complexity is O(n) ie size of the array.

Related questions

1 votes
1 votes
1 answer
1
Tuhin Dutta asked Dec 13, 2017
6,300 views
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.Is the above statement correct?
3 votes
3 votes
3 answers
4
firki lama asked Jan 12, 2017
13,319 views
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..