# Question: Find Nth fibonacci number in O(logN) time complexity.

Answer-1: We all know the Fibonacci recurrence as F(n+1) = F(n) + F(n-1) but we can represent this in the form a matrix as shown below:

Look at the matrix A = [ [ 1 1 ] [ 1 0 ] ] . Multiplying A with [ F(n) F(n-1) ] gives us [ F(n+1) F(n) ] , so we say that

A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ]

start with [ F(1) F(0) ] , multiplying it with A gives us [ F(2) F(1) ]; again multiplying [ F(2) F(1) ] with A gives us [ F(3) F(2) ] and so on...

A* [ F(1) F(0) ] = [ F(2) F(1) ]

A* [ F(2) F(1) ] = [ F(3) F(2) ] = A^2 * [ F(1) F(0) ]

A* [ F(1) F(0) ] = [ F(4) F(3) ] = A^3 * [ F(1) F(0) ]

A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ] = A^n * [ F(1) F(0) ]

So all that is left is finding the nth power of the matrix A. Well, this can be computed in O(log n) time, by recursive doubling. The idea is, to find A^n , we can do R = A^(n/2) * A^(n/2) and if n is odd, we need do multiply with an A at the end. The following pseudo code shows the same.

Matrix findNthPower( Matrix M , power n )

{

if( n == 1 ) return M;

Matrix R = findNthPower ( M , n/2 );

R = RxR; // matrix multiplication

if( n%2 == 1 ) R = RxM; // matrix multiplication

return R;

}

In this manner, by using the magic of DP, we can get the Nth fibonacci number in O(logN).

Answer-2: Doing the matrix exponential with an eigendecomposition first is exactly equivalent to JDunkerly's solution below. The eigenvalues of this matrix are the (1 + sqrt(5))/2 and (1 - sqrt(5))/2.

The nth Fibonacci number is given by
f(n) = Floor(phi^n / sqrt(5) + 1/2)
where
phi = (1 + sqrt(5)) / 2
Assuming that the primitive mathematical operations (+, -, * and /) are O(1) you can use this result to compute the nth Fibonacci number in O(log n) time (O(log n) because of the exponentiation in the formula).
In C#:
static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use
 const double inverseSqrt5 = 0.44721359549995793928183473374626
 const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
  return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

http://www.codechef.com/wiki/tutorial-dynamic-programming
http://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time
http://tech-queries.blogspot.com/search/label/Amazon%20Interview