Golden ratio or Pi in the running time

Question

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.

Answer 1

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.

Answer 2

(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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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