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)
“And Manuel embraced his mother and they laughed together: Délira’s laugh sounded surprisingly young; that was because she hadn’t really had the chance to make it heard; life was just not happy enough for that. No, she never had time to use it; she had kept it fresh as can be, like a birdsong in an old nest.”
—Jacques Roumain (1907–1945)