Double exponential function

See Big O notation for a comparison of the rate of growth of various functions.

A sequence of positive integers (or real numbers) is said to have double exponential rate of growth if the function giving the nth term of the sequence is bounded above and below by double exponential functions of n. Examples include Aho and Sloane observed that in several important integer sequences, each term is a constant plus the square of the previous term.

They show that such sequences can be formed by rounding to the nearest integer the values of a double exponential function with middle exponent 2.

[2] In computational complexity theory, 2-EXPTIME is the class of decision problems solvable in double exponential time.

It is equivalent to AEXPSPACE, the set of decision problems solvable by an alternating Turing machine in exponential space, and is a superset of EXPSPACE.

An example is Chan's algorithm for computing convex hulls, which performs a sequence of computations using test values hi = 22i (estimates for the eventual output size), taking time O(n log hi) for each test value in the sequence.

Thus, the overall time for the algorithm is O(n log h) where h is the actual output size.

Odd perfect numbers with n distinct prime factors are known to be at most

[7] The largest known prime number in the electronic era has grown roughly as a double exponential function of the year since Miller and Wheeler found a 79-digit prime on EDSAC1 in 1951.

Varfolomeyev and Gurevich[9] experimentally fit where N(y) is the population in millions in year y.

[10] Dendritic macromolecules have been observed to grow in a doubly-exponential fashion.