Mostly, for the functions in the fast growing hierachy, LOWER bounds are given like

$f_k(n) > 2 \uparrow^{k-1} n$

but what abour (reasonable tight) UPPER bounds ?

What are the best known UPPER bounds for $f_k(n)$ ?

The functions in the fast growing hierachy are defined as follows

$f_0(n) = n+1$

$f_{k+1} = f_k^n(n) = f_k(f_k(...n)...)$

where $f_k$ appears n times.

So $$f_1(n) = 2n$$ $$f_2(n) = n2^n$$ $$f_3(n) \ge 2 \uparrow 2 \uparrow ... \uparrow 2 \uparrow n$$

with n 2's

and so on.


closed as unclear what you're asking by Stefan Kohl, Ryan Budney, Boris Bukh, user9072, S. Carnahan Apr 30 '14 at 3:10

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What sort of notation do you want to use to express upper bounds when $k$ is large? At some point, you will need a recursive formula. $\endgroup$ – S. Carnahan Apr 30 '14 at 3:10

Browse other questions tagged or ask your own question.