how much time will fibonacci series will take to compute?

Question

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

There are efficient algorithms to calculate fibonacci numbers. All you need to do is to google a little before asking. — Yu Hao, Oct 21 '14 at 05:30

score 1 · Answer 1 · answered Oct 21 '14 at 05:41

1

You could have a "cache", where you save already computed Fibonacci numbers. Every time you try to compute

fib(n-1) /* or */ fib(n-2) ;

You would first look into your array of already computed numbers. If it's there, you save a whole lot of time. So every time you do compute a fibonacci number, save it into your array or list, at the corresponding index.

function fib(n) 
{

if (n =< 1) 
{
  return n;
}
if(fiboList[n] != defaultValue)
{
  return fiboList[n];
}
else 
{
    int fibo = fib(n-1) + fib(n-2);
    fiboList[n] = fibo;
    return fibo;
}

}

answered Oct 21 '14 at 05:41

Dagon313

46
4

what you mean by defaultValue here – Oct 21 '14 at 05:51
Whatever you choose, it could be -1 for example. – Dagon313 Oct 21 '14 at 06:22
The idea is you create an array, and initialize each number in that array with a defaultValue, like -1. So if array[n] is -1, you know that that specific Fibonacci number has not yet been computed. If you find a different value at array[n], that's the result of fibo[n] so you don't have to go all the recursive way. – Dagon313 Oct 21 '14 at 06:24

user · Accepted Answer · 2014-10-22T07:10:36.473

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.

score 0 · Answer 3 · edited Feb 11 '23 at 17:29

0

You can also do it by dynamic programming:

def fibo(n):
    dp = [0,1] + ([0]*n)
    def dpfib(n):
        return dp[n-1] + dp[n-2]
    for i in range(2,n+2):
        dp[i] = dpfib(i)
    return dp[n]

edited Feb 11 '23 at 17:29

Adrian Mole

49,934
160
51
83

answered Feb 09 '23 at 06:00

Karan Jadaun

1
1

how much time will fibonacci series will take to compute?

3 Answers3