Matrix Exponentiation

Fibonacci in O(log n)

1:00

How to compute linear recurrences such as Fibonacci in O(k³ log n) time by encoding the recurrence as a matrix and raising it to the n-th power with binary exponentiation.

By the end, you can

Explain why an O(n) loop is infeasible for very large n and why a logarithmic method is needed.
Construct the 2×2 companion matrix M for the Fibonacci recurrence and verify M·v = next state.
State the formula Mⁿ = [[F(n+1),F(n)],[F(n),F(n-1)]] and read F(n) from the correct entry.
Trace through binary exponentiation for a small exponent, identifying which rounds perform a result-multiply and which only square.
Derive the O(k³ log n) complexity from the cost per matrix multiply and the number of multiplications.
Identify which recurrences can and cannot be solved with matrix exponentiation.
Explain why the result matrix starts as the identity and when a plain loop may be faster for small n.

Up next in String Algorithms, Advanced DP & Competitive Techniques