Double exponential time
An algorithm is said to be double exponential time if T ( n ) is upper bounded by 22poly( n ), where poly( n ) is some polynomial in n . Such algorithms belong to the complexity class 2-EXPTIME. 2-EXPTIME = ⋃ c ∈ N DTIME ( 2 2 n c ) {\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)} Well-known double exponential time algorithms include: Decision procedures for Presburger arithmetic Computing a Gröbner basis (in the worst case) Quantifier elimination on real closed fields takes at least double exponential time, and can be done in this time.