Please help me with this with a clear explanation? Thanks
In class, we discussed about the two versions of Fibonacci number calculations: BinaryFib(n) and LinearFibonacci(n) (refer to your slides and the text book). The first algorithm has exponential time complexity, while the second one is linear. a) In this programming assignment, you will design an algorithm (in pseudo code), and implement (in Java), two recursive versions of an Oddonacci calculator (similar to the ones of Fibonacci) and experimentally compare their runtime performances. Oddonacci numbers are inspired by Fibonacci numbers but start with three predetermined values, each value afterwards being the sum of the preceding three values. The first few Oddonacci numbers are: 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745,25281, 46499, For that, with each implemented version you will calculate Oddonacci(5), Oddonacci (10), etc. in increments of 5 up to Oddonacci(100) (or higher value if required for your timing measurement) and measure the corresponding run times. For instance, Oddonacci(10) returns 105 as value. You can use Java's built-in time function for this purpose. You should redirect the output of each program to an out.txt file. You should write about your observations on the timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled files, and the text files b) Briefly explain why the first algorithm is of exponential complexity and the second one is linear (more specifically, how the second algorithm resolves some specific bottleneck(s) of the first algorithm). You can write your answer in a separate file and submit it together with the other submissions. c) Do any of the previous two algorithms use tail recursion? Why or why not? Explain your answer. If your answer is "No" then: Can a tail-recursive version of Od donacci calculator be designed ? i. If yes; write the corresponding pseudo code for that tail recursion algorithm and implement it in Java and repeat the same experiments as in part (a) above If no, explain clearly why such tail-recursive algorithm is infeasible. ii. You will need to submit both the pseudo code and the Java program, together with your experimental results. Keep in mind that Java code is not pseudo code. See full details of submission details below In class, we discussed about the two versions of Fibonacci number calculations: BinaryFib(n) and LinearFibonacci(n) (refer to your slides and the text book). The first algorithm has exponential time complexity, while the second one is linear. a) In this programming assignment, you will design an algorithm (in pseudo code), and implement (in Java), two recursive versions of an Oddonacci calculator (similar to the ones of Fibonacci) and experimentally compare their runtime performances. Oddonacci numbers are inspired by Fibonacci numbers but start with three predetermined values, each value afterwards being the sum of the preceding three values. The first few Oddonacci numbers are: 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745,25281, 46499, For that, with each implemented version you will calculate Oddonacci(5), Oddonacci (10), etc. in increments of 5 up to Oddonacci(100) (or higher value if required for your timing measurement) and measure the corresponding run times. For instance, Oddonacci(10) returns 105 as value. You can use Java's built-in time function for this purpose. You should redirect the output of each program to an out.txt file. You should write about your observations on the timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled files, and the text files b) Briefly explain why the first algorithm is of exponential complexity and the second one is linear (more specifically, how the second algorithm resolves some specific bottleneck(s) of the first algorithm). You can write your answer in a separate file and submit it together with the other submissions. c) Do any of the previous two algorithms use tail recursion? Why or why not? Explain your answer. If your answer is "No" then: Can a tail-recursive version of Od donacci calculator be designed ? i. If yes; write the corresponding pseudo code for that tail recursion algorithm and implement it in Java and repeat the same experiments as in part (a) above If no, explain clearly why such tail-recursive algorithm is infeasible. ii. You will need to submit both the pseudo code and the Java program, together with your experimental results. Keep in mind that Java code is not pseudo code. See full details of submission details below
