Recursionhard
0:00.0

The Fibonacci sequence can be computed using matrix exponentiation: (Fn+1Fn)=(1110)n(F1F0)\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} with F0=0,F1=1F_0 = 0, F_1 = 1. Using fast exponentiation to compute FnF_n, what is the time complexity?