Analyze the time complexity of the recursive Fibonacci algorithm in M3. Assignme

Question

Analyze the time complexity of the recursive Fibonacci algorithm in M3. Assignment 1 in terms of how many lines of code will be executed. Look very carefully at your recursive code. If you use an n of 5, how many lines of code will be executed?

Create a binary tree that stores your calls. How many calls will each internal node make? How many internal nodes will you have for a recursive version of the solution? Now, how big is that number? What if you call 5 “n” and think of Fib(n). What is the runtime complexity of your solution?

Explanation / Answer

Please find my answer:

Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.

Extra Space: O(n) if we consider the function call stack size, otherwise O(1).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.