The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ………
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
Fn = Fn-1 + Fn-2
with seed values
F0 = 0 and F1 = 1.
Method (Optimized Method)
The method can be optimized to work in O(Logn) time complexity.
// Fibonacci Series using Optimized Method
#include <bits/stdc++.h>
using namespace std;
void multiply( int F[2][2], int M[2][2]);
void power( int F[2][2], int n);
// Function that returns nth Fibonacci number
int fib( int n)
{
`` int F[2][2] = {{1, 1}, {1, 0}};
`` if (n == 0)
`` return 0;
`` power(F, n - 1);
`` return F[0][0];
}
// Optimized version of power() in method 4
void power( int F[2][2], int n)
{
`` if (n == 0 || n == 1)
`` return ;
`` int M[2][2] = {{1, 1}, {1, 0}};
``
`` power(F, n / 2);
`` multiply(F, F);
``
`` if (n % 2 != 0)
`` multiply(F, M);
}
void multiply( int F[2][2], int M[2][2])
{
`` int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
`` int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
`` int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
`` int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
``
`` F[0][0] = x;
`` F[0][1] = y;
`` F[1][0] = z;
`` F[1][1] = w;
}
// Driver code
int main()
{
`` int n = 9;
``
`` cout << fib(9);
`` getchar ();
``
`` return 0;
}
Output
34
Time Complexity: O(Logn)
Extra Space: O(Logn) if we consider the function call stack size, otherwise O(1).