# Fibonacci using Matrix Representation.

Fibonacci using matrix representation is of the form : Fibonacci Matrix. This claims to be of O(log n).However, isn't computing matrix multiplication of order O(n^3) or using Strassen's algorithm O(n^2.81)? How can this be solved in O(log n)?

• I suspect they use mathematical results specific to this (rather simple) matrix to produce a calculation that does not need the full blown matrix multiply and is, instead, only $O(\log{n})$. Commented Jul 14, 2016 at 14:57
• You mean to say that, this matrix is a special case of finding matrix exponentiation in 0(log n)? Commented Jul 14, 2016 at 15:08
• I'm saying that I suspect that the recurrence you get from the matrix multiply has some special property such that the result can be calculated without going through the full-blown matrix multiplication. I haven't done this myself, by the way. It's just my speculation. (Though I think it's well founded.) Its "$O$", by the way, not "zero". Commented Jul 14, 2016 at 16:47
• Those are completely different $n$'s. Computing the $n$-th Fibonacci number takes time $O(\log n)$. Multiplying two matrices of size $k$ takes time $O(k^{2.81})$. Commented Jul 14, 2016 at 19:02

Yes, using Fibonacci Matrix $\begin{pmatrix} 1&1\\1&0\end{pmatrix}$ is the way to calculate the nth fibonacci number in $O(log(n))$ time. You can apply this to the matrix, and the solution is reduced to $O(log(n))$.

I put an example code.

long long fibonacci(int n)
{
long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}};
int i,j,k;
while(n)
{
if(n&1)
{
memset(tmp,0,sizeof tmp);
for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]);
for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j];
}
memset(tmp,0,sizeof tmp);
for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]);
for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j];
n/=2;
}
return (ret[0][1]);
}


Matrix multiplication is $O(n^{2.81})$, where $n$ is the size of the matrix. The matrix size is constant here ($n = 2$). So each matrix multiplication takes constant time.

If we want $f_k$, there are $\log k$ matrix multiplications needed. Each takes constant time, so the total time is $O(\log k)$.