Editing Time complexity (section)

== Double exponential time ==
An algorithm is said to be [[double exponential function|double exponential]] time if ''T''(''n'') is upper bounded by 2<sup>2<sup>poly(''n'')</sup></sup>, where poly(''n'') is some polynomial in ''n''. Such algorithms belong to the complexity class [[2-EXPTIME]].
:<math>\textsf{2-EXPTIME} = \bigcup_{c \in \N} \textsf{DTIME}\left( 2^{2^{n^c}}\right)</math>

Well-known double exponential time algorithms include:
* Decision procedures for [[Presburger arithmetic]]
* Computing a [[Gröbner basis]] (in the worst case<ref>{{cite journal | last1 = Mayr | first1 = Ernst W. | author1-link = Ernst Mayr (computer scientist) | last2 = Meyer | first2 = Albert R. | author2-link = Albert R. Meyer | doi = 10.1016/0001-8708(82)90048-2 | issue = 3 | journal = [[Advances in Mathematics]] | mr = 683204 | pages = 305–329 | title = The complexity of the word problems for commutative semigroups and polynomial ideals | volume = 46 | year = 1982| doi-access = free | hdl = 1721.1/149010 | hdl-access = free }}</ref>)
* [[Quantifier elimination]] on [[real closed field]]s takes at least double exponential time,<ref>{{cite journal | last1 = Davenport | first1 = James H. | author1-link = James H. Davenport | last2 = Heintz | first2 = Joos|author2-link=Joos Ulrich Heintz | doi = 10.1016/S0747-7171(88)80004-X | issue = 1–2 | journal = [[Journal of Symbolic Computation]] | mr = 949111 | pages = 29–35 | title = Real quantifier elimination is doubly exponential | volume = 5 | year = 1988| doi-access = free }}</ref> and can be done in this time.<ref>{{cite conference | last = Collins | first = George E. | author-link = George E. Collins| editor-last = Brakhage | editor-first = H. | contribution = Quantifier elimination for real closed fields by cylindrical algebraic decomposition | doi = 10.1007/3-540-07407-4_17 | mr = 0403962 | pages = 134–183 | publisher = Springer | series = Lecture Notes in Computer Science | title = Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975 | volume = 33 | year = 1975| doi-access = free | isbn = 978-3-540-07407-6 }}</ref>