Question

I have the following program which returns F(n) for the fibonacci sequence both recursively and iteratively:

public class Fibonacci {
    //Recursive method
    public int fibRecursive(int n) {
        //If n is in the 0th or 1st place return n
        if (n <= 1)
            return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }
    //Iterative method
    public int fibIterative(int n) {
        if (n <= 1)
            return n;
        int fib = 1, prevFib = 1;
        for (int i = 2; i < n; i++) {
            int temp = fib;
            fib += prevFib;
            prevFib = temp;
        }
        return fib;
    }
    //Display and print running time
    public static void dispTime() {
        long startTime = System.nanoTime();
        System.out.println("t = " + (System.nanoTime() - startTime) + " nanosecs.");
    }

    public static void main(String[] args) {
        Fibonacci fib = new Fibonacci();
        Scanner input = new Scanner(System.in);

        System.out.println("Enter a value for n: ");
        int n = input.nextInt();

        System.out.println("Iterative version:");
        long startTime = System.nanoTime();
        System.out.println(fib.fibIterative(n));
        System.out.println("t = " + (System.nanoTime() - startTime) + " nanosecs.");

        System.out.println("Recursive version:");
        startTime = System.nanoTime();
        System.out.println(fib.fibRecursive(n));
        System.out.println("t = " + (System.nanoTime() - startTime) + " nanosecs.");
    }
}

I'm having trouble with the following questions:

3. Analysis:
For your recursive method:
(a) (10 points) What is the worst-case big-O running time with re-
spect to n? (Explain how you computed the running time, 0 points
if you do not say what is the basic operation counted and what
counting rules you used.)
(b) (10 points) Are your measurements consistent with this big-O
running time? (Explain using your measurements, 0 points if you
do not say something like \looking at row recursive, when n is
doubled the running time is xxx".)
For your non-recursive method:
(c) (10 points) What is the worst-case big-O running time with re-
spect to n? (Explain how you computed the running time, 0 points
if you do not say what is the basic operation counted and what
counting rules you used.)
(d) 10 points Are your measurements consistent with this big-O run-
ning time? (Explain using your measurements, 0 points if you do
not say something like \looking at row non-recursive, when n is
doubled the running time is xxx ").

Thank you!

Answer 1