4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Mar 7 '17 at 8:13
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.