Search code examples
time-complexitypseudocodefibonacci

how much time will fibonacci series will take to compute?

i have created the recursive call tree by applying brute force technique but when i give this algorithm 100 values it takes trillion of years to compute..

what you guys suggest me to do that it runs fast by giving 100 values

here is what i have done so far

function fib(n) {
    if (n =< 1) {
      return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}
Solution

  • You can do it also with a loop:

    int a = 1;
int b = 1;
for(int i = 2; i < 100; i++){
    int temp = a + b;
    a = b;
    b = temp;
}
System.out.println("Fib 100 is: "+b);

    The runtime is linear and avoids the overhead caused by the recursive calls.

    EDIT: Please note that the result is wrong. Since Fib(100) is bigger than Integer.MAX_VALUE you have to use BigInteger or similar to get the correct output but the "logic" will stay the same.