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:
“Well, I had gone and spoiled it again, made another mistake. A double one in fact. There were plenty of ways to get rid of that officer by some simple and plausible device, but no, I must pick out a picturesque one; it is the crying defect of my character.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“The daily arguments over putting away the toys or practicing the piano defeat us so easily. We see them coming yet they frustrate us time and time again. In many cases, we are mothers and fathers who have managed budgets and unruly bosses and done difficult jobs well through sheer tenacity and dogged preparation. So why are we unable to persuade someone three feet tall to step into six inches of water at bathtime?”
—Cathy Rindner Tempelsman (20th century)