Computation of Nth Fibonacci Number

Fibonacci Sequence

Fibonacci Sequence is the series of numbers which starts with two $1's$ in the beginning, then each number after that is the sum of two previous numbers in the sequence. So a fibonacci sequence is going to be:

1 1 2 3 5 8 13 21 34 .......

Computation of Nth Fibonacci Number

The definition of of Nth Fibonacci Number fib(n) is recursive in nature. i.e.

 
fib(n) = fib(n-2) + fib(n-1)
  

So the nth Fibonacci number can be easily computed using this recursive relation.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using Recursion
	*/
	public static long fib_recursion(int n) {
	if (n == 0) {
	return 0;
	}
	if (n == 1) {
	return 1;
	}
	return fib_recursion(n-2) + fib_recursion(n-1);
	} // fib
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Problem

The problem with this solution is we are going to be computing same computation over and over again.

As you can see from the recursion tree, fib() method is called multiple times for the same value. The time complexity of this solution is going to be ${\cal O}(2^n)$ and the space complexity if ${\cal O}(1)$.

Memoization Solution

Since we are computing same computation over and over again, we could store our intermediate result and use it instead of computing again.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using memoization
	*/
	public static long fib_memoization(int n, long[] mem) {
	if (n == 0 || n == 1) {
	mem[n] = n;
	return n;
	}
	if (mem[n] == 0) {
	mem[n] = fib_memoization(n-2, mem) + fib_memoization(n-1, mem);
	}
	return mem[n];
	} // fib
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Complexity

Time complexity of this solution is ${\cal O}(n)$ and the Space Complexity is also ${\cal O}(n)$.

Dynamic Programming - Bottom Up Solution

Similar to Memoization, we can also solve it using Dynamic Programming - Bottom Up Approach.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using DP
	*/
	public static long fib_dp(int n) {
	long[] dp = new long[n+1];
	for (int i = 0; i <= n; i++) {
	if (i == 0 || i == 1) {
	dp[i] = i;
	continue;
	}
	dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[n];
	} // fib3
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Complexity

Time complexity of this solution is ${\cal O}(n)$ and the Space Complexity is also ${\cal O}(n)$.

Modified Dynamic Programming

We can see in the dynamic programming that to compute next fibonacci number we use only Two of the previous results. So we can infer that we don't need to store all previous results. Its enough to store only two previous results. Following is the solution using this principle.

	//--------------------------------------------------------------------------
	/**
	* Compute nth Fibonacci number using modified DP
	*/
	public static long fib_dp_modified(int n) {
	if (n == 0 || n == 1) {
	return n;
	}
	long first = 0;
	long second = 1;
	int k = 2;
	do {
	long temp = first + second;
	first = second;
	second = temp;
	if (k == n) {
	return second;
	}
	k++;
	} while (true);
	} // fib4
	//--------------------------------------------------------------------------

view raw Fibonacci.java hosted with ❤ by GitHub

Complexity

Time complexity of this solution is ${\cal O}(n)$ and the Space Complexity is ${\cal O}(1)$.

---

---

---