24

I just tried implementing code (in Java) for various means by which the nth term of the Fibonacci sequence can be computed and I'm hoping to verify what I've learnt.

The iterative implementation is as follows:

public int iterativeFibonacci(int n)
{
  if ( n == 1 ) return 0;
  else if ( n == 2 ) return 1;
  int i = 0, j = 1, sum = 0;
  for ( ; (n-2) != 0; --n )
  {
    sum = i + j;
    i = j;
    j = sum;
  }
  return sum;
}

The recursive implementation is as follows :-

  public int recursiveFibonacci(int n)
  {
    if ( n == 1 ) return 0;
    else if ( n == 2 ) return 1;
    return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
  }

The memoized implementation is as follows :-

  public int memoizedFibonacci(int n)
  {
    if ( n <= 0 ) return -1;
    else if ( n == 1 ) return 0;
    else if ( n == 2 ) return 1;
    if ( memory[n-1] == 0 )
      memory[n-1] = memoizedFibonacci(n-1);
    if ( memory[n-2] == 0 )
      memory[n-2] = memoizedFibonacci(n-2);
    return memory[n-1]+memory[n-2];
  }

I'm having a bit of a doubt when trying to figure out the Big-O of these implementations. I believe the iterative implementation to be O(n) as it loops through N-2 times.

In the recursive function, there are values recomputed, hence I think it's O(n^2).

In the memoized function, more than half of the values are accessed based on memoization. I've read that an algorithm is O(log N) if it takes constant time to reduce the problem space by a fraction and that an algorithm is O(N) if it takes constant time to reduce the problem space by a constant amount. Am I right in believing that the memoized implementation is O(n) in complexity? If so, wouldn't the iterative implementation be the best among all three? (as it does not use the additional memory that memoization requires).

Nayuki
  • 17,911
  • 6
  • 53
  • 80
  • 1
    Linear recurence problems like these in programming competitions are usually solved via "matrix exponentiation". There's a C++ example for Fibonacci series in this [blogpost](http://fusharblog.com/solving-linear-recurrence-for-programming-contest/). – plesiv Nov 18 '12 at 12:30

2 Answers2

23

The recursive version is not polynomial time - it's exponential, tightly bounded at φn where φ is the golden ratio (≈ 1.618034). The recursive version will use O(n) memory (the usage comes from the stack).

The memoization version will take O(n) time on first run, since each number is only computed once. However, in exchange, it also take O(n) memory for your current implementation (the n comes from storing the computed value, and also for the stack on the first run). If you run it many times, the time complexity will become O(M + q) where M is the max of all input n and q is the number of queries. The memory complexity will become O(M), which comes from the array which holds all the computed values.

The iterative implementation is the best if you consider one run, as it also runs in O(n), but uses constant amount of memory O(1) to compute. For a large number of runs, it will recompute everything, so its performance may not be as good as memoization version.

(However, practically speaking, long before the problem of performance and memory, the number is likely to overflow even 64-bit integer, so an accurate analysis must take into account the time it takes to do addition if you are computing the full number).

As plesiv mentioned, the Fibonacci number can also be computed in O(log n) by matrix multiplication (using the same trick as fast exponentiation by halving the exponent at every step).

Community
  • 1
  • 1
nhahtdh
  • 55,989
  • 15
  • 126
  • 162
0

A java implementation to find Fibonacci number using matrix multiplication is as follows:

private static int fibonacci(int n)
{
    if(n <= 1)
        return n;

    int[][] f = new int[][]{{1,1},{1,0}};

    //for(int i = 2; i<=n;i++)
        power(f,n-1);

    return f[0][0];
}

// method to calculate power of the initial matrix (M = [][]{{1,1},{1,0}})

private static void power(int[][] f, int n)
{
    int[][] m = new int[][]{{1,1},{1,0}};

    for(int i = 2; i<= n; i++)
        multiply(f, m);


}

// method to multiply two matrices
private static void multiply(int[][] f, int[][] m)
{

    int x = f[0][0] * m[0][0] + f[0][1] * m[1][0];
    int y = f[0][0] * m[0][1] + f[0][1] * m[1][1];
    int z = f[1][0] * m[0][0] + f[1][1] * m[1][0];
    int w = f[1][0] * m[0][1] + f[1][1] * m[1][1];

    f[0][0] = x;
    f[0][1] = y;
    f[1][0] = z;
    f[1][1] = w;



}

Even another faster method than Matrix exponentiation method to calculate Fibonacci number is Fast Doubling method. The amortized time complexity for both the methods is O(logn). The method follows the following formula F(2n) = F(n)[2*F(n+1) – F(n)] F(2n + 1) = F(n)2 + F(n+1)2

One such java implementation for Fast Doubling method is as below:

private static void fastDoubling(int n, int[] ans)
{
    int a, b,c,d;

    // base case
    if(n == 0)
    {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }

    fastDoubling((n/2), ans);

    a = ans[0];  /* F(n) */
    b = ans[1];  /* F(n+1) */
    c = 2*b-a;

    if(c < 0)
        c += MOD;

    c = (a*c) % MOD;  /* F(2n)  */
    d = (a*a + b*b) % MOD ;  /*  F(2n+1) */

    if(n%2 == 0)
    {
        ans[0] = c;
        ans[1] = d;
    }
    else
    {
        ans[0] = d;
        ans[1] = (c+d);
    }

}
Paul92
  • 137
  • 2
  • 7