# Golden ratio or Pi in the running time

There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.

• Is there any particular computational reason to suspect that it might? And without knowing where it arises, do you think there's any particular insight to be gained if it does? Jan 7, 2013 at 18:25
• The golden ratio arises in the complexity analysis of programs that are similar in recursive structure to the recursion involved in the Fibonacci numbers: $F_{n+2} = F_{n+1} + F_n$. Jan 7, 2013 at 18:32
• The Fortnow and Melkebeek time/space lower-bound for SAT solvability contained the golden ratio ($n^{\phi - \epsilon}$ time and $n^{o(1)}$ space); but the exponent has been improved later by Ryan Williams. Jan 7, 2013 at 19:51
• @MarzioDeBiasi I think your comment makes a good answer, even if the result was improved. The interesting thing is that there is an analysis that yields the golden ratio in the exponent Jan 8, 2013 at 10:32
• @NieldeBeaudrap I hope to see some pattern among the examples. For example, the exponent e shows up in many places in randomized algorithms. I not surprised by that since I know that ball-and-bins kind of activity leads to answers which involve e. I was wondering if something like that can be said about algorithms that have golden ratio in the running times. Jan 11, 2013 at 12:12

It's the base rather than the exponent, but there's an $O(\varphi^k n^2)$ FPT time bound in

"An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization", Vida Dujmovic, Sue Whitesides, Algorithmica 40:15–31, 2004.

Also, it's a lower bound rather than an upper bound, but:

"An $n^{1.618}$ lower bound on the time to simulate one queue or two pushdown stores by one tape", Paul M.B. Vitányi, Inf. Proc. Lett. 21:147–152, 1985.

Finally, the one I was trying to find when I ran across those other two: the ham sandwich tree, a now-obsolete data structure in computational geometry for triangular range queries, has query time $O(n^{\log_2\varphi})\approx O(n^{0.695})$. So the golden ratio is properly in the exponent, but with a log rather than as itself. The data structure is a hierarchical partition of the plane into convex cells, with the overall structure of a binary tree, where each cell and its sibling in the tree are partitioned with a ham sandwich cut. The query time is determined by the recurrence $Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$, which has the above solution. It's described (with a more boring name) by

"Halfplanar range search in linear space and $O(n^{0.695})$ query time", Herbert Edelsbrunner, Emo Welzl, Inf. Proc. Lett. 23:289–293, 1986.

• I’m not sure I would be comfortable with saying that $n^{\log_2\varphi}=\varphi^{\log_2n}$ has $\varphi$ in the exponent. Feb 1, 2013 at 15:22

(from my comment above)

The Fortnow and Melkebeek time/space lower-bound for SAT solvability ($n^{\phi - \epsilon}$ time and $n^{o(1)}$ space) contained the golden ratio in the exponent; but it has been improved later by Ryan Williams.

• While Ryan Williams spoiled your Fortnow and Melkebeek example, he also provided another one in the same field: in cs.cmu.edu/~ryanw/automated-lbs.pdf , he shows that there is no alternation-trading proof of $\mathrm{coNTIME}[n]\nsubseteq\mathrm{NTIMESPACE}[n^{\phi+o(1)},n^{o(1)}]$. Jan 14, 2013 at 17:49

Also in the base rather than the exponent: the Monien-Speckenmeyer algorithm for 3-SAT has a running time of $\varphi^n\cdot O(n)$. That was the first non-trivial upper bound for 3-SAT.

Another example of $\varphi$ in the base is an algorithm by Andreas Björklund and Thore Husfeldt to compute the parity of the number of directed Hamiltonian cycles, which runs in time $O(\varphi^n)$.

http://arxiv.org/abs/1301.7250

Also in the base: The deletion–contraction algorithm (Zykov, 1949) for computing the number of graph colourings runs in time $O(\phi^{|E|+|V|})$. This is a very canonical example of how the golden ratio appears from a Fibonacci recurrence for the running time of evaluating a natural recursive formula; I’m sure it’s the oldest.

Mikko Koivisto found a $O(\phi^{|V|})$ algorithm for computing the number of perfect matchings (IWPEC 2009).

Golden ration in the base: A very recent FPT algorithm by Kociumaka and Pilipczuk, Faster deterministic Feedback Vertex Set computes a FVS of size $k$ in $O^*\left((2 + \phi)^k\right)$ time. (They then improves their algorithm to run in time $O^*(3.592^k)$.)

to expand on Martin Bergers comment: the ancient Euclidean GCD algorithm runs in worst case time on two successive elements from the Fibonacci sequence. more details on wikipedia which also states:

This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory,[93] and also the first practical application of the Fibonacci numbers.[91]

technically the GCD algorithm runs in logarithmic time $O(\log(n))$ but the golden ratio shows up in the number of steps of the algorithm.

[1] what is the time complexity of Euclids algorithm, math.se

• How is time and the number of steps different? Jan 31, 2013 at 20:53
• sorry that should read # of arithmetic operations
– vzn
Jan 31, 2013 at 22:56
• Lamé’s $\log_{\varphi}N$ bound is on the number of iterations of the main loop (or number of recursions, depending on the formulation of the algorithm). The running time of the algorithm is $O((\log N)^2)$ (that is, $O(n^2)$ in terms of the length of the input). Feb 1, 2013 at 15:19
• see the link. "let $T(a,b)$ be the number of steps taken in the Euclidean algorithm. $T(a,b)=O(log_\phi b)$"
– vzn
Feb 1, 2013 at 15:49
• I don’t know which of the links you mean, but anyway I’m simply clarifying what is the meaning of “step” here so that it makes sense. Note also that writing $O(\log_\phi b)$ is pointless, as logarithms in any two bases are $O$ of each other. Feb 1, 2013 at 19:01