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

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开发者_StackOverflow中文版 for this method to give an answer.

How can it be best achieved?

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.

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

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);
}