**Fibonacci** is the most famous sequence in the programming world.

It is defined by the following recursive formulation:

f(n)=f(n-1) + f(n-2) where f(0)=0 & f(1)=1.

The first few numbers of the sequence are:

0,1,1,2,3,5,8,13,21,34,55……

Program to find the N-Th Fibonacci number can be implemented iteratively or recursively very easily.But,for large values of N,we need an optimized algorithm.

**Using Recursion-**

[cpp]

fib(n)

{

if(n==0) return 0;

if(n==1) return 1;

return fib(n-1)+fib(n-2);

}

[/cpp]

This has an exponential time complexity.

**Using Iteration-**

[cpp]

fib(n)

{

if(n==0) return 0;

if(n==1) return 1;

a=0;

b=1;

for(i=2;i<=n;i++)

{

c=a+b;

a=b;

b=c;

}

return b;

}

[/cpp]

This code has a time complexity of O(N).

**Using power of the matrix{(0,0),(1,1)}-**

If we n times multiply the matrix M = {{1,1},{1,0}} to itself,then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.

|1 1|^n = | F(n+1) F(n) |

|0 1| | F(n) F(n-1)|

Result of exponentiation can be calculated using this method in O(logn).

[cpp]

/* 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 calculating power*/

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;

}

[/cpp]

This code has a time complexity of O(logN).