Nth Fibonacci

Iterative Solution - Brute Force

This is the simplest approach. Here, we declare a sum variable to keep track of the previous values. After calculating the sum, we swap the first and second values with the updated numbers.

1. Declare the first and second variables and initialize them to 0 and 1 respectively.
2. Start a loop from 2 (because we already have 0th and 1st values) and run it till target number.
3. Compute sum as first + second.
4. Make first = second and second = sum - Essentially updating the first and the second values.
5. Return sum at the end.

Time Complexity

• O(n) - Since we are going to loop till the number and perform constant time operations.

Recursive Approach.

The recursive approach is quite simple but has time complexity problems.

1. The base case for the recursive implementation will be when n is either equal to 0 or 1
2. If n === 0 return 0.
3. If n === 1 return 1.
4. Else, recurse the function with nthFibonacci(n - 1) + nthFibonacci(n - 2)

                F(4)
              /       \
          F(3)          F(2)
        /     \        /    \
     F(2)    F(1)   F(1)     F(0)
    /    \
  F(1)   F(0)  

The above tree like structure is formed in the call stack to compute the 4th fibonacci number.

Time Complexity:

• O(2^n) - Because to compute the nth iteration, 2^n nodes have to be created and visited.

Memoized Recursion

If you look at the recursive approach discussed previously,

                F(4)
              /       \
          F(3)          F(2)
        /     \        /    \
     F(2)    F(1)   F(1)     F(0)
    /    \
  F(1)   F(0)  

Here, we are trying to calculate F(1) - 3 Times, F(2) - 2 Times, F(0) - 2 times and so on.

The point is, the value of F(3) for example, will always be the same no matter how many times we compute it.

In these types of cases, Memoization comes into picture.

Memoization is nothing but a way for a function to remember or cache the results. Given an expensive function that takes a long time to compute for the same results, create a memorization function that can cache results and outputs them with no time at all.

1. Create a helper function fibonacciHelper(n, memo) - Where n is the nth fibonacci we are trying to calculate and memo is a simple hash-map or an object that will be initialized with:

Memo

{ 1: 0, 2: 1 }

2. The base case will be if n is present inside the memo object. If it is there, we simply return the results of that key - This is called memoization / remembering the resuts / caching.
3. Otherwise, we compute the results and store them in the memo object.
4. return memo[n] to return the last computed value.

Time Complexity

• O(n) - Because we essentially compute the values once, and return from cache whenever they're required AGAIN.