This lab is about timing different algorithms for calculating the nth fibonacci number.

I have given you code to show you how to time algorithms, as well as the first algorithm.

The algorithm I have given you is a recursive method for calculating fibonacci numbers.

For this lab you must write another method for calculating fibonacci numbers that is NOT recursive.

Then time both of these methods with a small, medium, and large number.

Write comments in your code with the resulting times and values.

Explain the trend in the times that you observed.

This is the code already provided:

public class Timer

$\{$

public static void main$($String$[]$ args$)$

$\{$

long startTime $=$ System.currentTimeMillis$()$;

$//$Code you want to time goes in between the System.currentTimeMillis calls.

$//$Feel free to duplicate this block to time more methods.

long endTime $=$ System.currentTimeMillis$()$;

System.out.println$($endTime $-$ startTime$)$;

$\}$

public static int fibRec$($int num$)$

$\{$

if $($num $<=2)$

return $1$;

return fibRec$($num $-1)+$ fibRec$($num $-2)$;

$\}$

public static int fibIter$($int num$)$

$\{$

$\}$

$\}$