Exploring Fibonacci

We all are familiar with Fibonacci numbers in the field of computer science. It is a sequence of integers which follows the pattern:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

The first two numbers in the sequence are 0 and 1. Any other number in the sequence is defined as:

Fn = Fn-1 + Fn-2

Here I will explore different ways of solving the Fibonacci numbers and the complexity associated with each of the algorithm.

Fibonacci Recursion

The easiest way of solving the Fibonacci is by recursion. Here is an example code snippet:

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

Complexity Analysis of Fibonacci Recursion

The time complexity of the Fibonacci recursive algorithm is measured by designating value of 1 to constant operations. 1 for comparing (n <= 1); 1 for fib1(n-1); 1 for fib2(n-2); and 1 for addition operation – fib1(n-1) + fib1(n-2).

T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2) + 4
T(n) = T(n-1) + T(n-2) + C -- equation (1)

To find the lower bound of time complexity, let’s assume

T(n-1) ≈ T(n-2)

then,

T(n) = 2T(n-2) + C
     = 2{2T(n-4) + C} + C
     = 4T(n-4) + 3C  -- equation (2)
     = 4{2T(n-6) + C} + 3C
     = 8T(n-6) + 7C -- equation (3) 
     = 16T(n-8) + 15C -- equation (4)

The equation can be re-written as,

T(n) = 2kT(n-2k) + (2k-1)C  -- equation (5)

Let’s verify if the expression holds true for all cases. In equation(2), k = 2; in equation(3), k = 3. Now if we want to apply equation (5) for n = 0:

T(n-2k)= T(0)
n-2k = 0
k = n/2 

Equation (5) can now be reduced to,

T(n) = 2n/2T(0) + (2n/2-1)C
T(n) = (1+C)2n/2 + C -- equation (6)

Now, we can say that the lower bound of time complexity is proportional to:

T(n) ∝ 2n/2 -- equation (7)

Similarly, we can find the upper bound of time complexity by assuming

T(n-2) ≈ T(n-1)

then,

T(n) = 2T(n-1) + C
     = 2{2T(n-2) + C} + C
     = 4T(n-2) + 3C  -- equation (7)
     = 4{2T(n-3) + C} + 3C
     = 8T(n-3) + 7C -- equation (8) 

The equation can be re-written as,

T(n) = 2kT(n-k) + (2k-1)C  -- equation(9)

For ,

T(n-k) = T(0)
n-k = 0
k = n

Equation (9) now can be reduced to,

T(n) = 2nT(0) + (2n-1)C
T(n) = (1+C)2n - C -- equation (10)

Now, we can say that the upper bound of time complexity is proportional to:

T(n) ∝ 2n -- equation (11)

So the time complexity of recursive Fibonacci algorithm is somewhere is between lower and upper bound of time complexity. However in Big-O terms, it is the upper bound of time complexity. In Big-O notation, the complexity of recursive Fibonacci algorithm is:

O(2n)

The recursive algorithm takes exponential time to compute the value. That’s a lot of time to derive a value. The Fibonacci recursion algorithm can be improved upon by applying the principle of dynamic programming.

Dynamic Programming

Dynamic Programming is a technique for solving problems which exhibit the characteristic of overlapping sub-problems. Let’s take the example of Fibonacci numbers. fib(n) is dependent on fib(n-1) and fib(n-2). To calculate fib(5), here is the number of times fib is called:fibonacci
You noticed that fib(3)  and fib(2) are called multiple times. We could have reused the value of fib(3) and fib(2) if we had stored the values during the first call. There are couple ways of storing the values. We will talk about it in the next couple of sections.

Memoization

It is similar to the recursive algorithm but with a small change. Now there is lookup table which the algorithm looks up before it computes a value. If the value exists, it doesn’t compute. Otherwise the value is computed and stored in the lookup table for later reuse. It’s the top down approach. Following is the memoized version of the Fibonacci number. I am restricting the array size to 1001. Any number bigger than 1000, will return a value of -1.

public class Fibonacci {
    public static int MAX = 1000;
    private int[] lookupTable = new int[MAX + 1];

    static {
        for (int i = 0; i <= MAX; i++) {
            lookupTable[i] = -1;
        }
        lookupTable[0] = 0;
        lookupTable[1] = 1;
    }

    public int fib2(int n) { 
        if (n > MAX) {
            return -1;
        }
    
        if (lookupTable[n] == -1) {
            lookupTable[n] = fib2(n-1) + fib2(n-2);
        } else {
            return lookupTable[n];
        }
    }
}

Complexity Analysis of Fibonacci Memoization

Though the complexity of memoized Fibonacci is still O(2n), it is much faster than regular Fibonacci recursion since we have reduced the time by defining the recursive algorithm in terms of overlapping sub-problems.

Tabulation

It is the bottom-up approach of solving a problem by building a table that returns the last entry from the table. In memoized version, the lookup table is filled on demand while all the entries in the tabulated version is filled up at once. The lookup table in memoized is not necessary filled up at a given instance.

public int fib3(int n) {
   int[] fib = new int[n + 1];
   fib[0] = 0;
   fib[1] = 1;

   for (int i = 2; i <= n; i++) {
       fib[i] = fib[i-1] + fib[i-2];
   } 
   return fib[n];
}

Complexity Analysis of Fibonacci Tabulation

The complexity is linear time, i.e, the amount of times around the loop is equal to the size of number, n, we are trying to calculate. The complexity is shown as O(n).

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s