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:

    “Freedom in art, freedom in society, this is the double goal towards which all consistent and logical minds must strive.”
    —Victor Hugo (1802–1885)

    “The writer who aims at producing the platitudes which are “not for an age, but for all time” has his reward in being unreadable in all ages.... The man who writes about himself and his own time is the only sort of man who writes about all people and about all time.”
    —George Bernard Shaw (1856–1950)