Can you please help me implement this on java(with the code please). Also can yo
ID: 3873691 • Letter: C
Question
Can you please help me implement this on java(with the code please). Also can you explain it step by step? thanks
I have NO clue what to do
rogramming Ouestions (50 marks In class, we discussed 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 in pseudo code and implement in Java two recursive versions of Tetranacci calculators and experimentally compare their runtime performances. Tetranacci numbers are a more general version of Fibonacci numbers and start with four predetermined terms, each term afterwards being the sum of the preceding four terms The first few Tetranacci numbers are 0, 0, 0,1, 1,2, 4, 8, 15,29, 56, 108, 208,401, 773, 1490, For that, with each implemented version you will calculate Tetranacci(5), Tetranacci(10), etc. in increments of 5 up to Tetranacci (100) (or higher value if required for your timing measurement) and measure the corresponding run times (for instance, Tetranacci(10) returns 56). 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 timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled executables, 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 COMP 352-Fall 2017 Assignment - page 2 of 3Explanation / Answer
// Tetranacci.java
public class Tetranacci {
// Recursive Approach
public static int tetranacci(int number) {
if ((number == 0) || (number == 1) || (number == 2)) // base cases
return 0;
else if(number == 3){
return 1;
}
// recursion step
return tetranacci(number - 1) + tetranacci(number - 2) + tetranacci(number-3) + tetranacci(number-4);
}
// Linear Approach
public static int linearTetranacci(int number){
int first = 0, second = 0, third = 0, fourth = 1, next = 0;
for(int i=0;i<=number;i++){
if(i<=2){
next = 0;
} else if(i==3){
next = 1;
}
else {
next = first + second + third + fourth;
first = second;
second = third;
third = fourth;
fourth = next;
}
}
return next;
}
public static void main(String[] args) {
System.out.println(tetranacci(10));
System.out.println(linearTetranacci(10));
}
}
/************************************************************************************************************/
(2) the first algorithm will be of exponential complexity. Because we are computing sub problems many times
for example consider
Tetranacci(6) = Tetranacci(5) + Tetranacci(4) + Tetranacci(3)+ Tetranacci(2);
now Tetranacci(5) can be written as Tetranacci(4) + Tetranacci(3)+ Tetranacci(2) + Tetranacci(1);
and Tetranacci(4) can be written as Tetranacci(3)+ Tetranacci(2) + Tetranacci(1) + Tetranacci(0);
So like that if you see we are computing Tetranacci(4), Tetranacci(3),Tetranacci(2) etc multiple times
so as the number n increases theses repeated computation also increases and gives exponential complexity.
Second Solution is obviously a linear solution as it holds a single for loop till number n . and doesn't grow exponentially and doesn't calculate repeatedly.