Bissoy.com
Doctors Medicines MCQs Q&A

What is the time complexity of the recursive implementation used to find the nth fibonacci term?

What is the time complexity of the recursive implementation used to find the nth fibonacci term? Correct Answer Exponential

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) : : : = 2k * T(n – k) This recurrence will stop when n – k = 0 i.e. n = k Therefore, T(n) = 2n * O(0) = 2n Hence, it takes exponential time. It can also be proved by drawing the recursion tree and counting the number of leaves.

Related Questions

What is the space complexity of the recursive implementation used to find the nth fibonacci term?
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?
Series: 45, 135, 255, 405, 585, 795 A = nth term and B = (n + 1)th term Based on the above logic which of the following option is true? I: Difference between the second term and first term is 30 less than the difference between the third term and second term. II: Difference between the terms is multiple of 3. III: B = 2A
For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. L̅1 (complement of L1) is recursive II. L̅2 (complement of L2) is recursive III. L̅1 is context-free IV. L̅1 ∪ L2 is recursively enumerable
Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?
Which of the following recurrence relations can be used to find the nth fibonacci number?
What is the time complexity of the above recursive implementation used to reverse a string?
What data structure would you mostly likely see in non recursive implementation of a recursive algorithm?
What data structure would you most likely see in non recursive implementation of a recursive algorithm?
What is the time complexity of the above recursive implementation of binary search?