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:
“I grew up confidently expecting to have a profession and earn my own living, and also confidently expecting to be married and have children. It was fifty-fifty with me. I was just as passionately determined to have children as I was to have a career. And my mother was the triumphant answer to all doubts as to the success of this double role. From my earliest memory she had more than half supported the family and yet she was supremely a mother.”
—Crystal Eastman (1881–1928)
“In today’s world parents find themselves at the mercy of a society which imposes pressures and priorities that allow neither time nor place for meaningful activities and relations between children and adults, which downgrade the role of parents and the functions of parenthood, and which prevent the parent from doing things he wants to do as a guide, friend, and companion to his children.”
—Urie Bronfenbrenner (b. 1917)