McqMate

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. |

741

0

Do you find this helpful?

1

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- 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