import java.math.*;

public class Fibonacci {

public static void main(String[] args) {

int m;

BigInteger fibNum;

int test = 45;

// String to int

m = Integer.parseInt("45");

BigInteger test2 = new BigInteger("45");

int t = test2.intValue();

zero = new BigInteger("0");

one = new BigInteger("1");

// Initialize the answers

result = new BigInteger[m];

result [0] = new BigInteger("1");

result [1] = new BigInteger("1");

for(int i = 2; i

result [i] = new BigInteger("0");

}

fibNum = theBigFib(m);

System.out.println(m + "th Fibonacci number from theBigFib("+ m +") " + "is " + fibNum);

System.out.println("Overload method theBigFib("+ t + ")" + " is " + theBigFib(t));

System.out.println("Slower Version of fibonacci(" + test + ") is " + fibonacci(test));

}

//Slower version

public static int fibonacci(int n) {

if (n

return 1;

} else {

return fibonacci(n - 1) + fibonacci(n - 2);

}

}

private static BigInteger one;

private static BigInteger zero;

private static BigInteger[] result;

// create fast theBigFib

public static BigInteger theBigFib(int n) {

// initialize result [0] to 1

if((n == 1) || (n == 2)) {

return result [0];

}

if(result [n - 1].compareTo(zero) != 0) {

return result [n - 1];

}

if(result [n - 2].compareTo(zero) == 0) {

result [n - 2] = theBigFib(n - 1);

}

if(result [n - 3].compareTo(zero) == 0) {

result [n - 3] = theBigFib(n - 2);

}

return result [n - 2].add(result [n - 3]);

}

}

Use the System clock (milliseconds) and demonstrate run-time complexity for Assignment #12 (Fibonacci) Are they O(N), or O(N 2), or 0(2AN), or O(NAN), 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) Create an Excel workbook of your results, and clearly (in titles) indicate your answers for Big-O. Your charts should have a title, label axes, a line that proposes your answer, and appropriate scales from zero to whatever is large enough to encompass your data. Everyone will have different data, but we should all come to the same Big-O conclusions, that fibonacci(test) is O??? and the BigFib(test2) is O??? You will likely start with some preliminary results, using just 8 or 10 elements as suggested in text, often getting slightly different results, something like Preliminary JPG In the end you will clean things up and get a more polished final chart that displays on the first worksheet along with your data FinalEst.JPG Crucial consideration: Big-O is the trend (slope) from small N to large N. theBigFib will use much larger N values for testing, as compared to the slow provided fibonacci method. Submit 2 files here: 1. your Testing.java program 2. your Excel workbook (xlxs)