What is the time complexity of computing a Fibonacci number of at least n?
It is known that
$$
\begin{bmatrix} 1 &amp; 1 \\ 1 &amp; 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} &amp; F_n \\ F_n &amp; F_{n-1} \end{bmatrix}.
$$
Using this, compute $F_1,F_2,F_4,\ldots,F_{2^m}$ until $F_{2^m} \geq n$. Then use binary search to recover the minimal Fibonacci number exceeding $n$.

Since $F_r$ grows exponentially in $r$, we have $2^m = \Theta(\log n)$ and so $m = \Theta(\log \log n)$. The algorithm thus runs in $O(\log\log n)$ steps. Each one involves calculation with numbers of size $O(\log n)$, so the overall complexity is $\tilde{O}(\log n)$.