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:
“O, my offense is rank, it smells to heaven;
It hath the primal eldest curse upon ‘t,
A brother’s murder. Pray can I not,
Though inclination be as sharp as will;
My stronger guilt defeats my strong intent,
And like a man to double business bound
I stand in pause where I shall first begin,
And both neglect. What if this cursed hand
Were thicker than itself with brother’s blood,
Is there not rain enough in the sweet heavens
To wash it white as snow?”
—William Shakespeare (1564–1616)
“As for the terms good and bad, they indicate no positive quality in things regarded in themselves, but are merely modes of thinking, or notions which we form from the comparison of things with one another. Thus one and the same thing can be at the same time good, bad, and indifferent. For instance music is good for him that is melancholy, bad for him who mourns; for him who is deaf, it is neither good nor bad.”
—Baruch (Benedict)