Wednesday, September 08, 2021

[xvvojqgz] slightly superexponential

factorial is a function that grows faster than any exponential but slower than n^n.  we explore other functions in this category.

side note: if you have a bound "a" on the base, (a+delta)^n grows faster than a^n.  the functions below are intended for dominating an exponential with unbounded but constant base.

a^n = exp(n * log a).  n^n = exp(n * log n).  we therefore explore exp(n * f(n)) where f(n) grows faster than a constant but slower than log n.

in decreasing rate of growth:

exp(n*(log(n) - a)) where a>0.  this is similar to factorial by Stirling approximation.  in Stirling, a=1 , and there is also a factor of sqrt(2pi*n).

exp(n*log(n)*a) where a<1

exp(n*(log(n))^a) where a<1

exp(n*(log(log(n))^a)) where a>1

exp(n*(log(log(n))*a)) where a>1

exp(n*(log(log(n))+a)) where a>0

exp(n*(log(log(n)+a))) where a is unrestricted

exp(n*(log(log(n))+a)) where a<0

exp(n*(log(log(n))*a)) where a<1

exp(n*(log(log(n))^a)) where a<1

although these functions grow faster than any exponential, they may overtake extremely slowly.  for example, exp(n*(log(log(n))^0.5)) exceeds 10^n around n = exp(201) = 10^87 .

simplified version, seeking functions that grow faster than a constant but slower than g(x)=x .

x - a where a>0

x*a where a<1

x^a where a<1

log(x)^a where a>1

log(x)*a where a>1

log(x)+a where a>0

log(x+a) where a is unrestricted

log(x)+a where a<0

log(x)*a where a<1

log(x)^a where a<1

No comments :