Objective: The goal of this assignment is to practice implementing iterative and
ID: 3734774 • Letter: O
Question
Objective: The goal of this assignment is to practice implementing iterative and recursive versions of Fibonacci number computation, and to learn about empirical performance testing to compare the speed of different algorithms. Assignment: Write the following two methods: 1.A method that computes the n-th Fibonacci number. The method must use an iterative algorithm (i.e., a for or while loop). The method header is as follows: long FiboIterative (int n) 2. A method that computes the n-th Fibonacci number using recursion (without caching of values to speed up the algorithm). The method header is as follows: long FiboRecursive(int n) The methods can be public/private or static as necessary. Note that we discussed these methods in the class. Your goal is to determine an empirical estimate of the efficiency of these two algorithms To do this you need to be able to calculate the execution time of a method. This can be done by using a system method to query the current system time before and after executing the method; the time elapsed is the difference between the two. In Java, you can use the method call System.currentTimeMillis) to get the time in milliseconds as a long. If the execution times are very small you can also use System.nanoTime). This method is not as accurate, but you can use it to get greater precision if you are consistently seeing millisecond times of 0 Start with the third Fibonacci number and compute up to the 50-th number in the series (or, compute it up to a number that is feasible in your computer using recursion). Here are the steps to perform: 1.Run the iterative algorithm, recording the elapsed time as described above for each Fibonacci number. To get an accurate estimate of the time taken for a specific you might need to call the method a number of times and average the resulting times 2. Run the recursive algorithm recording the elapsed time as described above for each Fibonacci number Generate a plot in Excel showing the performance trend of the two methods with different n. Put n on the x-axis and the average runtime on the y-axis. You can output the results to the console and copy the values into Excel by hand.Explanation / Answer
Answer.)
Code :
package com.example;
import java.util.Scanner;
public class FiboPerformanceTest {
public void iterativeFibonacci(int n){
int s=0,t=1,n3;
//printing 0 and 1
System.out.print(s+" "+t);
//loop starts from 2 because 0 and 1 are already printed
for(int i=2;i<n;++i)//loop starts from 2 because 0 and 1 are already printed
{
n3=s+t;
System.out.print(" "+n3);
s=t;
t=n3;
}
System.out.println();
}
public int recursiveFibonacci(int n){
if(n==0)
return 0;
if(n==1)
return 1;
else
return recursiveFibonacci(n-1)+recursiveFibonacci(n-2);
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("Enter the value of nth term:");
int n=sc.nextInt();
FiboPerformanceTest fiboPerformanceTest=new FiboPerformanceTest();
System.out.println("Fibonacci series in iterative approach:");
// starting time for iterative approach
long startIterative = System.currentTimeMillis();
fiboPerformanceTest.iterativeFibonacci(n);
// ending time for iterative approach
long endIterative = System.currentTimeMillis();
System.out.println("Fibonacci series using recursion:");
// starting time for recursive approach
long startRecursive = System.currentTimeMillis();
for(int i=0;i<n;i++){
System.out.print(fiboPerformanceTest.recursiveFibonacci(i)+" ");
}
// ending time for recursive approach
long endRecursive = System.currentTimeMillis();
System.out.println();
System.out.println("Time taken in iterative approach : "+(endIterative-startIterative)+"ms");
System.out.println("Time taken in recursive approach : "+(endRecursive-startRecursive)+"ms");
sc.close();
}
}
Output :
Enter the value of nth term:
25
Fibonacci series in iterative approach:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368
Fibonacci series using recursion:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368
Time taken in iterative approach : 1ms
Time taken in recursive approach : 10ms
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.