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.

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.

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.

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.

Complexity

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

---

---

---