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’ve been making love to a double dose of cyanide.”
—Robert Riskin (1897–1955)
“I love the smell of napalm in the morning. You know, one time we had to hailbomb, for twelve hours, and when it was all over I walked up.... We didn’t find one of ‘em, not one stinking dink
body. That smell, you know, that gasoline smell. The whole hill. It smelled like ... victory.”
—John Milius, U.S. screenwriter, Francis Ford Coppola (b. 1939)