Matrix Exponentiation

Raise a matrix to a power in $O(k^3\log n)$ to solve linear recurrences fast.

Advanced

The $n$ -th Fibonacci number in $O(\log n)$ via $\begin{pmatrix}1&1\\1&0\end{pmatrix}^n$ .

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)