Fibonacci using Dynamic Programming Questions and Answers

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Fibonacci using Dynamic Programming”.

1. The following sequence is a fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21,…..
Which technique can be used to get the nth fibonacci term?
a) Recursion
b) Dynamic programming
c) A single for loop
d) Recursion, Dynamic Programming, For loops
View Answer

Answer: d
Explanation: Each of the above mentioned methods can be used to find the nth fibonacci term.

2. Consider the recursive implementation to find the nth fibonacci number:

int fibo(int n)
    if n <= 1
	return n
    return __________

Which line would make the implementation complete?
a) fibo(n) + fibo(n)
b) fibo(n) + fibo(n – 1)
c) fibo(n – 1) + fibo(n + 1)
d) fibo(n – 1) + fibo(n – 2)
View Answer

Answer: d
Explanation: Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a fibonacci sequence would be given by:
fibo(n) = fibo(n-1) + fibo(n-2).

3. What is the time complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n²)
c) O(n!)
d) Exponential
View Answer

Answer: d
Explanation: The recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). So, the time complexity is given by:
T(n) = T(n – 1) + T(n – 2)
Approximately,
T(n) = 2 * T(n – 1)
= 4 * T(n – 2)
= 8 * T(n – 3)
:
:
:
= 2^k * T(n – k)
This recurrence will stop when n – k = 0
i.e. n = k
Therefore, T(n) = 2ⁿ * O(0) = 2ⁿ
Hence, it takes exponential time.
It can also be proved by drawing the recursion tree and counting the number of leaves.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

4. Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:

fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) 
+ fibonacci(3)	+ fibonacci(3) + fibonacci(2)
:
:
:

Which property is shown by the above function calls?
a) Memoization
b) Optimal substructure
c) Overlapping subproblems
d) Greedy
View Answer

Answer: c
Explanation: From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.

5. What is the output of the following program?

#include<stdio.h>
int fibo(int n)
{
      if(n<=1)
	 return n;
      return fibo(n-1) + fibo(n-2);
}
int main()
{   
      int r = fibo(50000);
      printf("%d",r); 
      return 0;
}

a) 1253556389
b) 5635632456
c) Garbage value
d) Runtime error
View Answer

Answer: d
Explanation: The value of n is 50000. The function is recursive and it’s time complexity is exponential. So, the function will be called almost 2⁵⁰⁰⁰⁰ times. Now, even though NO variables are stored by the function, the space required to store the addresses of these function calls will be enormous. Stack memory is utilized to store these addresses and only a particular amount of stack memory can be used by any program. So, after a certain function call, no more stack space will be available and it will lead to stack overflow causing runtime error.

6. What is the space complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
View Answer

Answer: a
Explanation: The recursive implementation doesn’t store any values and calculates every value from scratch. So, the space complexity is O(1).

7. Consider the following code to find the nth fibonacci term:

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   __________
  	   __________
       return curFib

Complete the above code.
a)

prevFib = curFib
curFib = curFib

prevFib = nextFib
curFib = prevFib

prevFib = curFib
curFib = nextFib

prevFib = nextFib
nextFib = curFib

View Answer

Answer: c
Explanation: The lines, prevFib = curFib and curFib = nextFib, make the code complete.

8. What is the time complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

a) O(1)
b) O(n)
c) O(n²)
d) Exponential
View Answer

Answer: b
Explanation: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

9. What is the space complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

a) O(1)
b) O(n)
c) O(n²)
d) Exponential
View Answer

Answer: a
Explanation: To calculate the nth term, we just store the previous term and the current term and then calculate the next term using these two terms. It takes a constant space to store these two terms and hence O(1) is the answer.

10. What will be the output when the following code is executed?

#include<stdio.h>
int fibo(int n)
{
      if(n==0)
         return 0;
      int i;
      int prevFib=0,curFib=1;
      for(i=1;i<=n-1;i++)
      {
           int nextFib = prevFib + curFib;
	   prevFib = curFib;
           curFib = nextFib;
      }
      return curFib;
}
int main()
{
      int r = fibo(10);  
      printf("%d",r);
      return 0;
}

a) 34
b) 55
c) Compile error
d) Runtime error
View Answer

Answer: b
Explanation: The output is the 10th fibonacci number, which is 55.

11. Consider the following code to find the nth fibonacci term using dynamic programming:

1. int fibo(int n)
2.   int fibo_terms[100000]  //arr to store the fibonacci numbers
3.   fibo_terms[0] = 0
4.   fibo_terms[1] = 1
5.		
6.   for i: 2 to n
7.	 fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.   return fibo_terms[n]

Which property is shown by line 7 of the above code?
a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure
View Answer

Answer: a
Explanation: We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.

12. Consider the following code to find the nth fibonacci term using dynamic programming:

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

Which technique is used by line 7 of the above code?
a) Greedy
b) Recursion
c) Memoization
d) Overlapping subproblems
View Answer

Answer: c
Explanation: Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.

13. What is the time complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

a) O(1)
b) O(n)
c) O(n²)
d) Exponential
View Answer

Answer: b
Explanation: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

14. What is the space complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

int fibo(int n)
        int fibo_terms[100000]  //arr to store the fibonacci numbers
        fibo_terms[0] = 0
	fibo_terms[1] = 1
 
	for i: 2 to n
		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
 
	return fibo_terms[n]

a) O(1)
b) O(n)
c) O(n²)
d) Exponential
View Answer

Answer: b
Explanation: To calculate the nth term, we store all the terms from 0 to n – 1. So, it takes O(n) space.

15. What will be the output when the following code is executed?

#include<stdio.
int fibo(int n)
{
      int i;
      int fibo_terms[100];
      fibo_terms[0]=0;
      fibo_terms[1]=1;
      for(i=2;i<=n;i++)
          fibo_terms[i] = fibo_terms[i-2] + fibo_terms[i-1];
      return fibo_terms[n];
}
int main()
{
      int r = fibo(8);
      printf("%d",r);
      return 0;
}