Analyze the time complexity of the recursive Fibonacci algorithm in M3. Assignme
ID: 3731773 • Letter: A
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).