What is the time complexity of computing a Fibonacci number of at least n?

Question

This is not the same as that classic time complexity problem about Fibonacci numbers your professor taught you in school. (That one asked for the time complexity of the nth Fibonacci number; I'd like the complexity of computing the Fibonacci sequence until encountering a value ≥ n.)

This arises in the data structure for ropes: the Boehm et al. paper on Ropes requires us to slot subtrees (containing subropes) into slots in the array; are numbered by their Fibonacci number¹:

1  2  3  5  8
↑        ↑
↑        subrope
subrope

That is, the slot labelled "3" holds a (single) rope whose length is in [3, 5).

A various points, we have leaves of (mostly) arbitrary size, which must then be slotted into a slot; thus, we need to compute which slot it goes into.

That algorithm is (mostly) trivial to write, but in terms of the number n, what is the running time of fibonacci_of_at_least(n)?

_{¹I've mirrored the diagram over a vertical line from how the Boehm et al. paper represented it; I frankly find the Boehm et al. paper's representation odd from a CS perspective, where the slot 1 is almost certainly going to be index 0 in an array in an implementation, and ergo belongs on the left.)}

_{The Boehm et al. paper mostly elides this problem: since the Fibonacci numbers we need correspond to the length of a string, we only need up to that length. 64-bits is ~100 numbers, and gets you out to exabyte string lengths. You can thus compute these in O(1) time, by just precomputing the table. However, I'm interested in the theoretically complexity.}

Answer 1

It is known that $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & 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)$.