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)
“Old hippies don’t die, they just lie low until the laughter stops and their time comes round again.”
—Joseph Gallivan (b. 1964)