Java (please show your program) Determine the largest values of n for which the corresponding Fibonacci Numbers can be computed within the given time.

n = _____ time required: less than 10 seconds

n = _____ time required: less than 30 seconds

n = _____ time required: less than 1 minute

n = _____ time required: less than 5 minutes

Estimate the value of n for the largest value of fib(n) that can be computed using recursion in one hour on your computer. Explain in detail how you estimated this value. Also describe any additional data you took to arrive at this value. Attach any additional work required.

n = ______ for time required = 1 hour (3600 seconds)

Repeat this problem for the largest value of n for which the corresponding Fibonacci number can be computed in one day (86,400 seconds).

n = ______ for time required = 1 day (86,400 seconds)

Repeat this problem for the largest value of n for which the corresponding Fibonacci number can be computed in one year.

n = ______ for time required = 1 year.

Repeat this problem for the largest value of n for which the corresponding Fibonacci number can be computed in one million years (10⁶years).

n = ______ for time required = 1 million years.

Memoization

The time complexity is exponential so this simplistic recursive approach becomes intractable when we get into the fifties or so. We can greatly increase our time performance with memoization that is, every time we compute a value we make a note (or memo) of it and check that memo list before computing.

Add memoization to your Fibonacci program. At what point does the computation time become more than one second?