In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy, or a Schwichtenberg-Wainer hierarchy)[1] is an ordinal-indexed family of rapidly increasing functions fα: N → N (where N is the set of natural numbers {0, 1, ...}, and α ranges up to some large countable ordinal).
(An alternative definition takes the number of iterations to be n+1, rather than n, in the second line above.)
The initial part of this hierarchy, comprising the functions fα with finite index (i.e., α < ω), is often called the Grzegorczyk hierarchy because of its close relationship to the Grzegorczyk hierarchy; note, however, that the former is here an indexed family of functions fn, whereas the latter is an indexed family of sets of functions
Using Buchholz psi functions one can extend this definition easily to the ordinal of transfinitely iterated
The Wainer hierarchy is the particular fast-growing hierarchy of functions fα (α ≤ ε0) obtained by defining the fundamental sequences as follows [Gallier 1991][Prӧmel, et al., 1991]: For limit ordinals λ < ε0, written in Cantor normal form, and Some authors use slightly different definitions (e.g., ωα+1[n] = ωα(n+1), instead of ωαn), and some define this hierarchy only for α < ε0 (thus excluding fε0 from the hierarchy).