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

**Answer:**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(3) F(2) ] = [ 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 multiplicationif( n%2 == 1 ) R = RxM; // matrix multiplicationreturn R;}

**PS:**This question was asked me in Amazon Interview and I could not replied it that time. I got this answer here and sharing the same.

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
UnknownSir, i don't think its dynamic programming

Akash@Sahil: It's not...

gauravalgoits better coded form is seen here

http://algosolver.blogspot.com/2011/09/fibonacci-log-n.html

DigitsBy mistake, in the first greyed section third line, its < A* [ F(1) F(0) ] = [ F(4) F(3) ] = A^3 * [ F(1) F(0) ] > while it should be < A* [ F(3) F(2) ] = [ F(4) F(3) ] = A^3 * [ F(1) F(0) ] >

Akash@Digits: Thanks buddy, corrected!

Ivan KadiyskiHere is an excellent solution

Nᵗʰ Fibonacci Number - Matrices Multiplication

The IndiaWe have highly experienced developer for the best SEO friendly websites for all types of businesses and can help make it profitable at the most economical rates.

SEO Sydney

Web Design Company

periyannanThis is a great post. I like this topic.This site has lots of advantage.I found many interesting things from this site. It helps me in many ways.Thanks for posting this again.

python internship | web development internship |internship for mechanical engineering students |mechanical engineering internships |java training in chennai |internship for 1st year engineering students |online internships for cse students |online internship for engineering students |internship for ece students |data science internships