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:
“You spotted snakes with double tongue,
Thorny hedgehogs, be not seen.
Newts and blindworms, do no wrong,
Come not near our Fairy Queen.”
—William Shakespeare (1564–1616)
“English people apparently queue up as a sort of hobby. A family man might pass a mild autumn evening by taking the wife and kids to stand in the cinema queue for a while and then leading them over for a few minutes in the sweetshop queue and then, as a special treat for the kids, saying “Perhaps we’ve time to have a look at the Number Thirty-One bus queue before we turn in.””
—Calvin Trillin (b. 1940)