3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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})$. $\endgroup$ Commented Jul 14, 2016 at 14:57
  • $\begingroup$ You mean to say that, this matrix is a special case of finding matrix exponentiation in 0(log n)? $\endgroup$ Commented Jul 14, 2016 at 15:08
  • $\begingroup$ 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". $\endgroup$ Commented Jul 14, 2016 at 16:47
  • 1
    $\begingroup$ 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})$. $\endgroup$
    – mjqxxxx
    Commented Jul 14, 2016 at 19:02

2 Answers 2

1
$\begingroup$

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]);
}
$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .