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:
“One key, one solution to the mysteries of the human condition, one solution to the old knots of fate, freedom, and foreknowledge, exists, the propounding, namely, of the double consciousness. A man must ride alternately on the horses of his private and public nature, as the equestrians in the circus throw themselves nimbly from horse to horse, or plant one foot on the back of one, and the other foot on the back of the other.”
—Ralph Waldo Emerson (1803–1882)
“I know, it must have been my imagination, but it makes me realize how desperately alone the Earth is. Hanging in space like a speck of food floating in the ocean. Sooner or later to be swallowed up by some creature floating by.... Time will tell, Dr. Mason. We can only wait and wonder. Wonder how, wonder when.”
—Tom Graeff. Young astronomer, Teenagers from Outer Space, after just seeing the invading spaceship through his telescope, and dismissing it (1959)