Assignment 3 >

Write the Java source code necessary to build a solution for the problem below: 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 Fibin),. What is the runtime complexity of your solution? Do you think you can do better if you simply do away with the recursion and calculate the Fibonacci series iteratively? Write a non-recursive solution and perform a similar analysis on it. How many lines of code would you execute in terms of "n"? Is it better or worse? Why do you think this is true? Hand in your non-recursive solution and a two page description of your analysis