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:
“...the shiny-cheeked merchant bankers from London with eighties striped blue ties and white collars and double-barreled names and double chins and double-breasted suits, who said “ears” when they meant “yes” and “hice” when they meant “house” and “school” when they meant “Eton”...”
—John le Carré (b. 1931)
“I am the family face;
Flesh perishes, I live on,
Projecting trait and trace
Through time to times anon,
And leaping from place to place
Over oblivion.”
—Thomas Hardy (1840–1928)