Fibonacci using Matrix Representation.

Question

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)?

Answer 1

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]);
}

Answer 2

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)$.