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:
“Society’s double behavioral standard for women and for men is, in fact, a more effective deterrent than economic discrimination because it is more insidious, less tangible. Economic disadvantages involve ascertainable amounts, but the very nature of societal value judgments makes them harder to define, their effects harder to relate.”
—Anne Tucker (b. 1945)
“...I’m thirteen years old, and I think I’m at the crossroads of my life. I’ve got to make good between now and the time I’m twenty, and I have only seven years to do it in. Besides, I’m the father of my family and I’ve got to earn all the money I can.”
—Mary Pickford (1893–1979)