Nth fibonacci number in O(logN) | PROGRAMMING INTERVIEWS
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...
Read full article from Nth fibonacci number in O(logN) | PROGRAMMING INTERVIEWS
No comments:
Post a Comment