# Fibonacci term in logarithmic time

Fibonacci Sequence are quite popular and there are many applications for the same in computer science. But how would you compute it’s **nᵗʰ** term in logarithmic time.

Fibonacci Sequence is series of number: 0, 1, 1, 2, 3, 5 …..

Mathematically this can be denoted as

Some common techniques for calculating **nᵗʰ **term

- Recursive approach( time complexity: exponential )
- Dynamic Programming approach( time complexity: linear time with linear space usage)
- Linear time and constant space solution, which keeps track of only previous two terms, unlike DP solution, thus making the space complexity constant.

Now we will go though a logarithm solution for the same, that can be used to find higher order terms.

We will utilize the following equation

now apply this function recursively, and we will end up with some thing like

Thus if we can find **nᵗʰ power of A** in **log(n)** time, we can have a **log(n) **solution for **nᵗʰ term of Fibonacci sequence**.

Here is the algorithm to compute **nᵗʰ power of A** in **log(n)** time

**I** be the identity matrix

*Power(A,n)*

Y = I

while(n > 0)

if (n is odd)

Y = MM(Y,A)

A = MM(A,A)

n = n/2

return Y

Here **MM** is the utility function to multiply two matrices.

Thus by combining equation in Fig 2 and logarithmic power finding algorithm, we can compute **nᵗʰ** term in logarithmic time.