# Are there any algorithms that run in (2 ↑ ↑ n)?

I’m wondering whether there are any algorithms that use so much time that they must be represented using Knuth up-arrow notation.

Required: Use more than one up-arrow for time complexity.

Bonus points:

• Have the algorithm be useful.

• Have the algorithm be useful and optimized

• If you don't mind artificial problems, there are some. For example, define sets $S_0 = \emptyset$ and $S_n = \{0, 1\}^{S_{n-1}} = \{f : S_{n-1} \rightarrow \{0, 1\}\}$. Brute force search over $S_n$ would take tetrative time. – Solomonoff's Secret Jul 12 '18 at 17:19

Yes! A simple automaton-based algorithm for answering first-order queries in Presburger arithmetic (and some extensions) has worst-case running time about $2 \uparrow\uparrow n$, where $n$ is the number of quantifier alternations in the query. Despite this formidable worst-case running time the algorithm has been implemented and gives useful results (see Hamoon Mousavi's implementation here).
For any computable function $f$, there are trivially algorithms that run in time $\Omega(f)$:
If, in addition, $f$ is time-constructible, the above algorithm runs in time $\Theta(f(n))$.