Question

. Fibonacci sequence Fn is defined as follows: F1 = 1; F2 = 1; Fn = Fn−1 + Fn−2, ∀n ≥ 3. A pseudocode is given below which returns n’th number in the Fibonacci sequence. RecursiveFibonacci(n) 1 if n = 0 2 return 0 3 elseif n = 1 or n = 2 4 return 1 5 else 6 a = RecursiveFibonacci(n − 1) 7 b = RecursiveFibonacci(n − 2) 8 return a + b Derive the complexity of the above algorithm by writing the recurrence and solving it. Use the memoization idea (of dynamic programming) to obtain a linear time algorithm for the above problem. Show Pseudo-code and complexity proof. (5 + 10)

Answer 1

Memoization is a technique to save the previously calculated values in an array so that we don't calculate them again.

Start with an array of size n with all elements 0.

First time a new value is calculated, add it to the array called memo. Initially check if the value exists in the array memo, if it does return the value if not calculate and add to array.

Pseudo code is here :

RecursiveFibonacci(n)
int memo[n] = {0}
if n = 0
   memo[0] = 0
   return 0
elseif n = 1 or n = 2
   memo[1] = memo[2]=1
   return 1
  
else
   if(memo[n]==0){
       a = RecursiveFibonacci(n − 1)
       b = RecursiveFibonacci(n − 2)
       memo[n] = a+b;
   }
return memo[n]