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.
Golden ratio or Pi in the running time
reference request;big list
It's the base rather than the exponent, but there's an $O(\varphi^k n^2)$ FPT time bound inAn Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization, Vida Dujmovic, Sue Whitesides, Algorithmica 40:1531, 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. Vitnyi, Inf. Proc. Lett. 21:147152, 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) byHalfplanar range search in linear space and $O(n^{0.695})$ query time, Herbert Edelsbrunner, Emo Welzl, Inf. Proc. Lett. 23:289293, 1986.