- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- Which of the following recurrence relati...

Q. |
## Which of the following recurrence relations can be used to find the nth fibonacci number? |

A. | f(n) = f(n) + f(n – 1) |

B. | f(n) = f(n) + f(n + 1) |

C. | f(n) = f(n – 1) |

D. | f(n) = f(n – 1) + f(n – 2) |

Answer» D. f(n) = f(n – 1) + f(n – 2) | |

Explanation: the relation f(n) = f(n – 1) + f(n – 2) can be used to find the nth fibonacci number. |

View all MCQs in:
Design and Analysis of Algorithms

- What is the time complexity of the recursive implementation used to find the nth fibonacci term?
- What is the space complexity of the recursive implementation used to find the nth fibonacci term?
- Which of the following methods can be used to find the nth Catalan number?
- We can solve any recurrence by using Master’s theorem.
- You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
- What is the result of the recurrences which fall under second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
- What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
- What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k?
- What will be the recurrence relation of the code of recursive selection sort?
- Recurrence equation formed for the tower of hanoi problem is given by

Login to Continue

It will take less than 2 minutes

Report MCQ