# 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. – Reinstate Monica 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).

• Nice! This type of answer was exactly what I was looking for! I only didn’t require the usefulness parameter because I thought it may not be possible! – JSCoder says Reinstate Monica Jul 13 '18 at 20:55

For any computable function $f$, there are trivially algorithms that run in time $\Omega(f)$:

x := f(n);
for i = 1 to x do [nothing];


If, in addition, $f$ is time-constructible, the above algorithm runs in time $\Theta(f(n))$.

I forego my bonus points, since the above is neither useful nor optimized.