Time Complexity - Double Exponential Time

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:

    Was it the double of my dream
    The woman that by me lay
    Dreamed, or did we halve a dream
    Under the first cold gleam of day?
    William Butler Yeats (1865–1939)

    As you are entered with the class of Nat. philosophy, give to it the hours of lecture, but devote all your other time to Mathematics, avoiding company as the bane of all progress.
    Thomas Jefferson (1743–1826)