In computational complexity theory, the complexity class E L E M E N T A R Y {\displaystyle {\mathsf {ELEMENTARY}}} consists of the decision problems that can be solved in time bounded by an elementary recursive function. The most quickly-growing elementary functions are obtained by iterating an exponential function such as 2 n {\displaystyle 2^{n}} for a bounded number k {\displaystyle k} of iterations, 2 2 2 ⋅ ⋅ ⋅ n } k . {\displaystyle \left.{\begin{matrix}2^{\scriptstyle 2^{\scriptstyle 2^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle n}}}}}}\end{matrix}}\right\}k.}

Thus, E L E M E N T A R Y {\displaystyle {\mathsf {ELEMENTARY}}} is the union of the classes

E L E M E N T A R Y = ⋃ k ∈ N k - E X P = D T I M E ( 2 n ) ∪ D T I M E ( 2 2 n ) ∪ D T I M E ( 2 2 2 n ) ∪ ⋯ . {\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots .\end{aligned}}}

It is sometimes described as iterated exponential time, though this term more commonly refers to time bounded by the tetration function.

This complexity class can be characterized by a certain class of "iterated stack automata", pushdown automata that can store the entire state of a lower-order iterated stack automaton in each cell of their stack. These automata can compute every language in E L E M E N T A R Y {\displaystyle {\mathsf {ELEMENTARY}}} , and cannot compute languages beyond this complexity class. The time hierarchy theorem implies that E L E M E N T A R Y {\displaystyle {\mathsf {ELEMENTARY}}} has no complete problems.

Every elementary recursive function can be computed in a time bound of this form, and therefore every decision problem whose calculation uses only elementary recursive functions belongs to the complexity class E L E M E N T A R Y {\displaystyle {\mathsf {ELEMENTARY}}} .