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:
“No slavery can be abolished without a double emancipation, and the master will benefit by freedom more than the freed-man.”
—Thomas Henry Huxley (1825–95)
“For the first time I’m content to see
What poor mortar and bricks
I have to build with, knowing that I can
Never in seventy years be more a man
Than now a sack of meal upon two sticks.”
—Philip Larkin (1922–1986)