<p>(from my comment above)</p>

<p>The <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.6228&amp;rep=rep1&amp;type=ps">Fortnow and Melkebeek</a> 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 <a href="http://www.cs.cmu.edu/~ryanw/ccc05.pdf">improved later by Ryan Williams</a>.</p>

CC BY-SA 3.0
2013-01-14T17:49:28.320Z
While Ryan Williams spoiled your Fortnow and Melkebeek example, he also provided another one in the same field: in http://www.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)}]$.
Emil Jeřábek
CC BY-SA 3.0
2013-01-08T16:46:12.333Z
2013-01-08T16:46:12.333Z
Marzio De Biasi
<p>Also in the base rather than the exponent: the <a href="http://dx.doi.org/10.1016/0166-218X%2885%2990050-2">Monien-Speckenmeyer algorithm</a> for 3-SAT has a running time of $\varphi^n\cdot O(n)$. That was the first non-trivial upper bound for 3-SAT. </p>

CC BY-SA 3.0
2013-01-08T08:47:10.293Z
2013-01-08T08:47:10.293Z
Jan Johannsen
<p>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)$.</p>

<p><a href="http://arxiv.org/abs/1301.7250">http://arxiv.org/abs/1301.7250</a></p>

CC BY-SA 3.0
2013-01-31T15:13:34.217Z
2013-01-31T15:13:34.217Z
Tyson Williams
<p>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. </p>

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

CC BY-SA 3.0
2013-02-05T08:00:13.420Z
2013-02-05T08:00:13.420Z
Thore Husfeldt
<p>Golden ration in the base: A very recent FPT algorithm by Kociumaka and Pilipczuk, <a href="http://arxiv.org/abs/1306.3566">Faster deterministic Feedback Vertex Set</a> 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)$.)</p>

CC BY-SA 3.0
2013-06-21T22:41:47.420Z
2013-06-21T22:41:47.420Z
vb le
<p>to expand on Martin Bergers comment: the ancient <a href="http://en.wikipedia.org/wiki/Euclidean_algorithm" rel="nofollow noreferrer">Euclidean GCD algorithm</a> runs in worst case time on two successive elements from the Fibonacci sequence. more details on <a href="http://en.wikipedia.org/wiki/Euclidean_algorithm#Worst-case_number_of_steps" rel="nofollow noreferrer">wikipedia</a> which also states: </p>

<blockquote>
  <p>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]</p>
</blockquote>

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

<p>[1] <a href="https://math.stackexchange.com/questions/258596/what-is-the-time-complexity-of-euclids-algorithm-upper-bound-lower-bound-and-a">what is the time complexity of Euclids algorithm</a>, math.se</p>

CC BY-SA 3.0
2013-01-31T20:53:38.603Z
How is time and the number of steps different?
Nicholas Mancuso
CC BY-SA 3.0
2013-01-31T22:56:33.680Z
sorry that should read # of arithmetic operations
vzn
CC BY-SA 3.0
2013-02-01T15:19:00.617Z
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).
Emil Jeřábek
CC BY-SA 3.0
2013-02-01T15:49:30.163Z
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
CC BY-SA 3.0
2013-02-01T19:01:40.240Z
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.
Emil Jeřábek
CC BY-SA 3.0
2013-02-01T19:17:41.417Z
re log bases, of course, agreed. $\phi$ arises in an _exact_ count of steps of the algorithm. the original question didnt insist on big-Oh. seems a fair/close case.
vzn
CC BY-SA 3.0
2013-01-31T17:27:30.230Z
2013-01-31T17:27:30.230Z
2017-04-13T12:19:19.363Z
vzn
<p>It's the base rather than the exponent, but there's an $O(\varphi^k n^2)$ FPT time bound in</p>

<p>"<a href="http://dx.doi.org/10.1007/s00453-004-1093-2">An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization</a>", Vida Dujmovic, Sue Whitesides, <em>Algorithmica</em> 40:15–31, 2004.</p>

<p>Also, it's a lower bound rather than an upper bound, but:</p>

<p>"<a href="http://dx.doi.org/10.1016/0020-0190%2885%2990020-1">An $n^{1.618}$ lower bound on the time to simulate one queue or two pushdown stores by one tape</a>", Paul M.B. Vitányi, <em>Inf. Proc. Lett.</em> 21:147–152, 1985.</p>

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

<p>"<a href="http://dx.doi.org/10.1016/0020-0190%2886%2990088-8">Halfplanar range search in linear space and $O(n^{0.695})$ query time</a>", Herbert Edelsbrunner, Emo Welzl, <em>Inf. Proc. Lett.</em> 23:289–293, 1986.</p>

CC BY-SA 3.0
2013-02-01T15:22:19.633Z
I’m not sure I would be comfortable with saying that $n^{\log_2\varphi}=\varphi^{\log_2n}$ has $\varphi$ in the exponent.
Emil Jeřábek
CC BY-SA 3.0
2013-01-07T22:02:13.690Z
2013-01-09T00:01:06.640Z
2013-01-09T00:01:06.640Z
David Eppstein
<p>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.</p>

CC BY-SA 3.0
2013-01-07T18:25:29.010Z
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?
Niel de Beaudrap
CC BY-SA 3.0
2013-01-07T18:32:03.147Z
The golden ratio arises in the complexity analysis  of programs that are similar in recursive structure  to the recursion involved in the [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio): $F_{n+2} = F_{n+1} + F_n$.
Martin Berger
CC BY-SA 3.0
2013-01-07T19:51:37.210Z
The [Fortnow and Melkebeek](http://dl.acm.org/citation.cfm?id=792765.793435) 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.
Marzio De Biasi
CC BY-SA 3.0
2013-01-08T10:32:37.243Z
@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
Sasho Nikolov
CC BY-SA 3.0
2013-01-11T12:12:18.263Z
@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.
Plummer
CC BY-SA 3.0
2013-01-31T21:19:52.820Z
FWIW, there are many approximation algorithms whose _approximation ratios_ contain interesting numbers (e.g. $\pi^2/6$, $e/(e-1)$, etc.)
Neal Young
<reference-request><big-list>
Golden ratio or Pi in the running time
Plummer
# Golden ratio or Pi in the running time

(Asked by: username_0 on 2013-01-07)

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.

**Tags:** reference-request, big-list
> **Comments:**
> **username_1**: 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?  
> **username_2**: The golden ratio arises in the complexity analysis  of programs that are similar in recursive structure  to the recursion involved in the [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio): $F_{n+2} = F_{n+1} + F_n$.  
> **username_3**: The [Fortnow and Melkebeek](http://dl.acm.org/citation.cfm?id=792765.793435) 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.  
> **username_4**: @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  
> **username_0**: @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.  
> **username_5**: FWIW, there are many approximation algorithms whose _approximation ratios_ contain interesting numbers (e.g. $\pi^2/6$, $e/(e-1)$, etc.)  

---

## 7 answers

### Answer by username_13 on 2013-01-07. Score: 22 | Accepted answer

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](http://dx.doi.org/10.1007/s00453-004-1093-2)", 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](http://dx.doi.org/10.1016/0020-0190%2885%2990020-1)", 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](http://dx.doi.org/10.1016/0020-0190%2886%2990088-8)", Herbert Edelsbrunner, Emo Welzl, *Inf. Proc. Lett.* 23:289–293, 1986.

> **Comments:**
> **username_6**: I’m not sure I would be comfortable with saying that $n^{\log_2\varphi}=\varphi^{\log_2n}$ has $\varphi$ in the exponent.  

---

### Answer by username_3 on 2013-01-08. Score: 18

(from my comment above)

The [Fortnow and Melkebeek](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.6228&rep=rep1&type=ps) 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](http://www.cs.cmu.edu/~ryanw/ccc05.pdf).

> **Comments:**
> **username_6**: While Ryan Williams spoiled your Fortnow and Melkebeek example, he also provided another one in the same field: in http://www.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)}]$.  

---

### Answer by username_7 on 2013-01-08. Score: 15

Also in the base rather than the exponent: the [Monien-Speckenmeyer algorithm](http://dx.doi.org/10.1016/0166-218X%2885%2990050-2) 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 by username_8 on 2013-01-31. Score: 10

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 by username_9 on 2013-02-05. Score: 9

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 by username_10 on 2013-06-21. Score: 8

Golden ration in the base: A very recent FPT algorithm by Kociumaka and Pilipczuk, [Faster deterministic Feedback Vertex Set](http://arxiv.org/abs/1306.3566) 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)$.)


---

### Answer by username_11 on 2013-01-31. Score: -2

to expand on Martin Bergers comment: the ancient [Euclidean GCD algorithm](http://en.wikipedia.org/wiki/Euclidean_algorithm) runs in worst case time on two successive elements from the Fibonacci sequence. more details on [wikipedia](http://en.wikipedia.org/wiki/Euclidean_algorithm#Worst-case_number_of_steps) 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](https://math.stackexchange.com/questions/258596/what-is-the-time-complexity-of-euclids-algorithm-upper-bound-lower-bound-and-a), math.se

> **Comments:**
> **username_12**: How is time and the number of steps different?  
> **username_11**: sorry that should read # of arithmetic operations  
> **username_6**: 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).  
> **username_11**: see the link. "let $T(a,b)$ be the number of steps taken in the Euclidean algorithm. $T(a,b)=O(log_\phi b)$"  
> **username_6**: 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.  
> **username_11**: re log bases, of course, agreed. $\phi$ arises in an _exact_ count of steps of the algorithm. the original question didnt insist on big-Oh. seems a fair/close case.  

---

