@ritesh1340

Lets start with the understanding that Fn = Fn-1 + Fn-2

Consider this beautiful matrix

|1 1|

|1 0|

Lets multiply it with a matrix and see what we get. **Here x, y, z are three consecutive fibonacci numbers such that z > y > z.**

|z y| |1 1|

|y x| |1 0|

The resulting matrix is

|z+y z+0|

| x+y y+0|

Here z+y is the newest addition to the series! Note that, x+y = z. We have basically created a new matrix but with the same quality of three consecutive fibonaccis.

Considering first three fibs are 0,1,1 - we just need to multiply following matrix as many times as needed with itself to get our result:

|11|

|10|

Square it and we get 4th fib. Cube it and we get 5th fib.

Now suppose you want me to find out the fib number 36. How much effort will I take?

Matrix square will give me 4th fib.

The above matrix square gives power of 4 -> 6th fib.

The above matrix square will give power of 8 -> 10th fib.

Square of above will give power of 16 -> 18th fib

Square of above will give power of 32 -> 34th fib.

Multiply above with what we got in step number 2 i.e. power of 34 -> 36th fib.

This happens in just 6 steps!

The compexity is visibly O(logn)

Hope it helps!