Submit FibDriver.java and write whether they are O(N), or O(N^2), or O(2^N), or O(N^N), or O(1), or O(N!), or ??? for these two algorithms, where N is the number of Fibonacci numbers generated. One is very fast (so you test with huge N values), and the one provided in the problem statement is very slow (can hardy get past N of 50).

Change code from FibDriver.java so we can calculate 10 random Fibonacci numbers for BigFib and BigFastFib to compare the System Clock (milliseconds) instead of having to write it multiple times to get different Fibonacci numbers: Can use a "for loop", "random" and "array list" to generate random fibonacci numbers.

import java.math.BigInteger;

public class FibDriver {

public static void main(String[] args) {

Fibonacci test = new Fibonacci(0); // only needed for overload

//BIGFIB ----- takes a longer time to get output

long currentTime = System.currentTimeMillis(); test.bigFib(new BigInteger("45"));

long afterCalTime = System.currentTimeMillis();

System.out.println((afterCalTime - currentTime) + " milliseconds to compute bigFib.");

//having to repeat the same code to get time for a different fib number

currentTime = System.currentTimeMillis();

test.bigFib(new BigInteger("150"));

afterCalTime = System.currentTimeMillis();

System.out.println((afterCalTime - currentTime) + " milliseconds to compute bigFib.");

//BIGFASTFIB ------ takes a shorter time to get output

currentTime = System.currentTimeMillis();

test.bigFastFib(new BigInteger("45"));

afterCalTime = System.currentTimeMillis();

System.out.println((afterCalTime - currentTime) + " milliseconds to compute bigFastFib.");

//having to repeat the same code to get time for a different fib number

currentTime = System.currentTimeMillis();

test.bigFastFib(new BigInteger("150"));

afterCalTime = System.currentTimeMillis();

System.out.println((afterCalTime - currentTime) + " milliseconds to compute bigFastFib.");

}

}

This is the Fibonacci.java for BigFib and BigFastFib:

import java.math.BigInteger; public class Fibonacci { // fields, ONE is in any version of Java already // but BigInteger.TWO requires Java 9 or higher, so I make one here private final BigInteger TWO = new BigInteger("2"); private final BigInteger ONE = new BigInteger("1"); private int n; // the boring old 32-bit limited int // only one constructor needed public Fibonacci(int number) { n = number; }

// using BigInteger // This allows us to go up to any size integer public BigInteger bigFib() { return bigFib(new BigInteger(Integer.toString(n))); } // recursive helper private BigInteger bigFib(BigInteger n) { if (n.compareTo(TWO)<=0) { return ONE; } else { return bigFib(n.subtract(ONE)).add(bigFib(n.subtract(TWO))); } } //FASTER BigInteger RESURSIVE METHOD //"public bigFastFib" method public BigInteger bigFastFib() { if (n <= 2) { return ONE; } else { return bigFastFib(new BigInteger(Integer.toString(n)), new BigInteger("3"), ONE, ONE); } } private BigInteger bigFastFib(BigInteger n, BigInteger i, BigInteger prev, BigInteger curr) { if (n.compareTo(i)==0) { return prev.add(curr); } else { return bigFastFib(n, i.add(ONE), curr, prev.add(curr)); } } }