I have a question about the time complexity of finding the nth Fibonacci number using matrices.
I know that you can find $F_n$ from:
$
\begin{pmatrix}
1 & 1\\
1 & 0\\
\end{pmatrix}^n = \begin{pmatrix}
F_{n+1} & F_n\\
F_n & F_{n-1}\\
\end{pmatrix}
$
From above, $F_n$ is the entry in row 1, column 2 of the matrix. I have read in an online source that raising the Fibonacci Q-matrix to the power of n takes O(n) time. I am not sure why this is the case. Is matrix multiplication an operation that can be done in constant time on computers? That is the only reason I can see the above operation taking O(n) time (since you would have to do n-1 multiplications to raise the Q-matrix to the power of n). Any insights are appreciated.
Best Answer
Multiplying two $2\times 2$ matrices can be done with eight multiplications and four additions, so yes, that is constant time. (In fact it can be done in fewer multiplications at the cost of more additions, but the point remains.)
Multiplying a $2\times 2$ matrix by $\begin{pmatrix}1 & 1\\1 & 0\\\end{pmatrix}$ can be done with just two additions, which is even faster.
But computing $F_n$ using $F_n=F_{n-1}+F_{n-2}$ takes just one addition, so why use matrices at all?
The answer is that computing $M^n$ for a matrix $M$ can actually be done using $O(\log n)$ multiplications and additions, using exponentiation by squaring. Check it out!