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:
“On the death of a friend, we should consider that the fates through confidence have devolved on us the task of a double living, that we have henceforth to fulfill the promise of our friend’s life also, in our own, to the world.”
—Henry David Thoreau (1817–1862)
“I feel free as a bird. I’m in a unique position because I’m the boss. I buy what I like. I initiate things. I can experiment with all kinds of things I think the kids might be interested in. Nobody interferes. For me, it’s no chore to go to work. Most people never get to do this at any time in their lives.”
—Sarah Houghton, U.S. librarian. As quoted in Working, book 9, by Studs Terkel (1973)