21
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ 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? $\endgroup$ – Niel de Beaudrap Jan 7 '13 at 18:25
  • 13
    $\begingroup$ 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$. $\endgroup$ – Martin Berger Jan 7 '13 at 18:32
  • 11
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Jan 7 '13 at 19:51
  • 2
    $\begingroup$ @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 $\endgroup$ – Sasho Nikolov Jan 8 '13 at 10:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Plummer Jan 11 '13 at 12:12
22
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I’m not sure I would be comfortable with saying that $n^{\log_2\varphi}=\varphi^{\log_2n}$ has $\varphi$ in the exponent. $\endgroup$ – Emil Jeřábek Feb 1 '13 at 15:22
18
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 5
    $\begingroup$ 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)}]$. $\endgroup$ – Emil Jeřábek Jan 14 '13 at 17:49
15
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
10
$\begingroup$

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

|cite|improve this answer
$\endgroup$
9
$\begingroup$

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

|cite|improve this answer
$\endgroup$
8
$\begingroup$

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

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How is time and the number of steps different? $\endgroup$ – Nicholas Mancuso Jan 31 '13 at 20:53
  • $\begingroup$ sorry that should read # of arithmetic operations $\endgroup$ – vzn Jan 31 '13 at 22:56
  • 1
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Feb 1 '13 at 15:19
  • $\begingroup$ see the link. "let $T(a,b)$ be the number of steps taken in the Euclidean algorithm. $T(a,b)=O(log_\phi b)$" $\endgroup$ – vzn Feb 1 '13 at 15:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 1 '13 at 19:01

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.