Fibonacci Number

In mathematics, the Fibonacci series is defined by the following recurrence relation:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
i.e. nth element is formed by adding elements at (n-1) and (n-2)
So, first 10 fibonacci numbers will be:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Given a number n, find F(n).
Example:
Input: 6
Output: 8
Input: 10
Output: 55


Video coming soon!



Subscribe for more updates


Algorithm/Insights

Recursive Solution:
1. Boundary Condition: If n = 0 or n = 1, return n
2. Return F(n-1) + F(n-2)
F(n-1) = F(n-2) + F(n-3)
We see that F(n-2) will be computed again for F(n-1). So, a lot of redundant calculations.
Time Complexity: Exponential

Efficient Solution:
The problem can be solved by Dynamic Programming because it has both the properties:
1. Overlapping Subproblems -
        As F(n) = F(n-1) + F(n-2), computation of nth fibonacci number requires (n-1) and (n-2) fibonacci numbers.
        Further F(n-1) = F(n-2) + F(n-3), and so on
        So, we see that there are overlapping sub problems.
2. Optimal Substructure -
        If subproblems F(n-1) and F(n-2) are computed optimally, then the solution to F(n) is also optimal. Hence it satisfies optimal substructure property.
So, if we store the solutions to subproblems here, we can find next fibonacci number efficiently without computing the values again.
Also, as F(n) = F(n-1) + F(n-2), we need only the last 2 values of the series to find the next value. Hence, we do not need to store all subproblem solutions but only the previous 2 i.e. F(i-1) and F(i-2). Once we have F(i), for calculating F(i+1) we just need F(i) and F(i-1), and therefore we can discard F(i-2) as it is not needed further.
So starting with F(0) = 0, F(1) = 1, we can use bottom up approach to calculate F(n)
1. Boundary Condition: If n = 0 or n = 1, return n
2. Take a = 0, b = 1
3. Loop n-2 times, and calculate
   c = a+b
   a = b
   b = c
4. Return c


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * In Fibonacci sequence, given a number n, find the F(n).
 * Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...
 * Input: 6
 * Output: 8
 *
 * @author Saurabh
 */
public class Fibonacci {

	// Recursive Solution
	// Time complexity: Exponential
	public static int getFibonacciRec(int n) {
		if(n < 0) {
			throw new IllegalArgumentException("n cannot be negative!");
		}
		if(n == 0 || n == 1) 
			return n;
		return getFibonacciRec(n-1) + getFibonacciRec(n-2);
	}
	
	public static int getFibonacci(int n) {
		if(n < 0) {
			throw new IllegalArgumentException("n cannot be negative!");
		}
		if(n == 0 || n == 1) 
			return n;
		int a = 0, b = 1;
		int c = a+b;
		for(int i = 2; i <= n; i++) {
			c = a+b;
			a = b;
			b = c;
		}
		return c;
	}

	public static void main(String[] args) {
		//System.out.println(getFibonacciRec(6));
		System.out.println(getFibonacci(6));
	}
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.


    Saurabh Kumar