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.
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 doubly exponential time (but is not even known to be computable in ELEMENTARY)
Read more about this topic: Time Complexity
Famous quotes containing the words double and/or time:
“I met Jack Kennedy in November, 1946.... We went out on a double date and it turned out to be a fair evening for me. I seduced a girl who would have been bored by a diamond as big as the Ritz.”
—Norman Mailer (b. 1923)
“In a time of war the nation is always of one mind, eager to hear something good of themselves and ill of the enemy. At this time the task of news-writers is easy, they have nothing to do but to tell that a battle is expected, and afterwards that a battle has been fought, in which we and our friends, whether conquering or conquered, did all, and our enemies did nothing.”
—Samuel Johnson (1709–1784)