<p>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$.</p>

<p>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)$.</p>

CC BY-SA 3.0
2017-03-07T07:34:07.127Z
2017-03-07T07:34:07.127Z
Yuval Filmus
<p>This is <em>not</em> 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 <em>n</em>th Fibonacci number; I'd like the complexity of computing the Fibonacci sequence until encountering a value ≥ <em>n</em>.)</p>

<p>This arises in the data structure for ropes: <a href="https://en.wikipedia.org/wiki/Rope_(data_structure)" rel="noreferrer">the Boehm et al. paper on Ropes</a> requires us to slot subtrees (containing subropes) into slots in the array; are numbered by their Fibonacci number¹:</p>

<pre><code>1  2  3  5  8
↑        ↑
↑        subrope
subrope
</code></pre>

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

<p>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.</p>

<p>That algorithm is (mostly) trivial to write, but in terms of the number <em>n</em>, what is the running time of <code>fibonacci_of_at_least(n)</code>?</p>

<p><sub>¹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.)</sub></p>

<p><sub>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.</sub></p>

CC BY-SA 3.0
2017-03-07T08:13:42.047Z
Isn't it enough to just take the closed form for Fibonacci, and rewrite the equation?  $F_n$ is the closest integer to $\phi^n/\sqrt{5}$, hence to find $n$ s.t. $F_n \geq x$, one can compute $\log (x\times \sqrt{5})/\log \phi$, and this is ±1 the correct value.
Michaël Cadilhac
<time-complexity>
What is the time complexity of computing a Fibonacci number of at least n?
Thanatos
# What is the time complexity of computing a Fibonacci number of at least n?

(Asked by: username_0 on 2017-03-07)

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 *n*th 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](https://en.wikipedia.org/wiki/Rope_(data_structure)) 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.

**Tags:** time-complexity

> **Comments:**
> **username_1**: Isn't it enough to just take the closed form for Fibonacci, and rewrite the equation?  $F_n$ is the closest integer to $\phi^n/\sqrt{5}$, hence to find $n$ s.t. $F_n \geq x$, one can compute $\log (x\times \sqrt{5})/\log \phi$, and this is ±1 the correct value.  

---

## 1 answers

### Answer by username_2 on 2017-03-07. Score: 5

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)$.


---

