Fibonacci Finding (easy)
Fibonacci Numbers
Fibonacci Numbers are
Fibonacci numbers are generated using the following recurrence relation
It is interesting to note that the Fibonacci number grows so fast that exceeds the 32-bit signed integer range.
The fastest way to accurately compute Fibonacci numbers is by using a matrix-exponentiation method.
We need to calculate to calculate the Nth fibonacci number. We can calculate it in using fast exponentiation.
Simple Recursive Solution
fibonacci(n)
if(n=0)
return 0
if (n=1)
return 1
return (fibonacci(n-1)+fibonacci(n-2))
Time complexity:
Optimization using Dynamic Programming
There are only n overlapping subproblems which can be stored to reduce the time complexity to
//Initialize all elements in dp to -1
fibonacci(n)
if(dp[n]!=-1)
return dp[n]
if(n=0)
dp[n]=0
else if (n=1)
dp[n]=1
else
dp[n]=fibonacci(n-1)+fibonacci(n-2)
return dp[n]
Time Complexity =
Space Complexity =
Using Matrix Exponentiation
//Calculating A^p in O(log(P))
Matrix_pow ( Matrix A,int p )
if(p=1)
return A
if(p%2=1)
return A*Matrix_pow(A,p-1)
Matrix B = Matrix_pow(a,p/2);
return B * B
fibonacci(n)
if(n=0)
return 0;
if(n=1)
return 1;
Matrix M[2][2]={{1,1},{1,0}}
Matrix res=matrix_pow(M,n-1);
return res[0][0];
Time Complexity =