CODEWITHSUNDEEP
algorithmmathmatrixfibonacci
Setu Kumar Basak
Setu Kumar Basak

Reputation: 12022

Finding Nth Fibonacci Number in O(logn) time and space complexity?

I am trying to find the Nth Fibonacci number in O(logn) time. We can do O(logn) solution by using the Fibonacci Q matrix.

enter image description here

But, there is another solution by using the Cassini and Catalan identities to find the Nth Fibonacci number in O(logn) time. It states below:

If n is even then k = n/2: F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2: F(n) = F(k)*F(k) + F(k-1)*F(k-1)

I could understand the proof only upto the marked equation:

enter image description here

But, I am not understanding the below equations and the final derived equations.

Can anyone please explain in details? Thanks in Advance.

Upvotes: 1

Views: 1227

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

I believe the idea is to take this matrix product

 |1 1|^n   |1 1|^m    |1 1|^{m+n}
 |1 0|   x |1 0|    = |1 0|

and use the fact that this can be rewritten as

 |F_{n+1}    F_n    |   |F_{m+1}    F_m    |   |F_{m+n+1}    F_{m+n}  |
 |                  | x |                  | = |                      |
 |F_n        F_{n-1}|   |F_m        F_{m-1}|   |F_{m+n}      F_{m+n-1}|

Now, multiply the matrices on the left using the standard matrix product formula. You get this reuslt:

|F_{n+1} F_{m+1} + F_n F_m    F_{n+1}F_m + F_n F_{m-1}  |   |F_{m+n+1}    F_{m+n}  |
|                                                       | = |                      |
|F_n F_{m+1} + F_{n-1} F_m    F_n F_m + F_{n-1} F_{m-1} |   |F_{m+n}      F_{m+n-1}|

This gives these four equations:

  • Fn+1Fm+1 + FnFm = Fm+n+1
  • Fn+1Fm + FnFm-1 = Fm+n
  • FnFm+1 + Fn-1Fm = Fm+n
  • FnFm + Fn-1Fm-1 = Fm+n-1

The remaining equalities fall out from just substituting in specific values of m and n.

Upvotes: 1

Related Questions