Fibonacci number time complexity

Question

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 

Comments

B..

---

@Soumya Tiwari and @ adarsh_1997 ji

can you explain, please?

---

USE TREE METHOD FOR SOLVING ABOVE CODE T(n)=T(n-1)+t(n-2)+c

AND FOR DYNAMIC APPROACH JUST CREATE A TABLE WHICH WILL BE USED TO STORE REPEATED SUBPROBLEMS.SO IT WILL BE 0(N).

Answer 1

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

Answer 2

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.