How to return the time, which would take for a method to finish it's job?

Question

I have a simple recursive algorithm, which returns Fibonacci numbers:

private static double fib_recursive(int n){
    if(n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

Now my task is to return the time, which this method would take to calculate the 400-th fibonacci number on a given computer e.g. fib_recursive(400). "Would" is in bold, because I can't run the function, as it would take to long for this method to give an answer.

How can it be best achieved?

Answer 1

Calculate how much time to do each recursive call, figure out how many recursive calls, and you have an answer.

There are faster ways to do this, using a smarter recursion algorithm, but for your algorithm just put in some timing information.

Answer 2

Timing is done by taking differences of System.currenTimeMillis() or System.nanoTime() before and after what you want to meausre.

Answer 3

I ended up with probably not a best solution, but here is what i've got(may be it will help someone in future):

1) I measured the time, which the recursive method needs to calculate the 42-nd(for example) Fibonacci number.

2) Using the iterative method, I counted how many program rows are executed while calculating the 42-nd Fibonacci number with the recursive method. (Rows = 3*fib_iterative(42)-2)

3) Deviding 2. by 1. I got the average number of rows executed in 1 millisecond.

4) Using the iterative method, I counted how many program rows are executed while calculating the 400-th Fibonacci number with the recursive method. (Rows = 3*fib_iterative(400)-2)

5) Deviding 4. by 3. I got the estimated time spent by fib_recursive(400).

// Recursive algorithm, calculates Fibonacci number (slow)
private static double fib_recursive(int n){
    if( n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

// Iterative algorithm, calculates Fibonacci number (fast)
private static double fib_iterative(int n){
    double a = 1, b = 1;
    for (int i = 2; i <= n; i++){
        b = a + b;
        a = b - a;
    }
    return a;
}

// Get time, which fib_recursive(int) needs to calculate the 400th Fibonacci number
private static long testRecursiveFor400(){
    int elapsedTime = 0;
    int start = (int) System.currentTimeMillis();
    fib_recursive(42);
    elapsedTime = (int) (System.currentTimeMillis() - start);
    return (3 * (long) fib_iterative(400) - 2) / ((3 * (int) fib_iterative(42) - 2) / elapsedTime);
}