Is there a function that grows faster than exponentially but slower than a factorial?

In big-O notation the complexity class O(2n) is named “exponential”. The complexity class O(n!) is named “factorial”.

I believe that f(n)=O(2n) and g(n)=O(n!) means that f(n)g(n) goes to zero in the limit as n goes to infinity.

Is there any known function between the factorial and exponential complexity classes?

In other words is there any known function j(n) that dominates every function in O(2n), such that:
(j(n)O(2n))(j(n)=O(n!))(n!O(j(n)))
or, informally, j(n) grows asymptotically strictly faster than 2n but not as fast as n!?

Or perhaps it has been proven that no such function can exist?

Note: this may seem like a Computer Science question, but in fact I am attempting to prove that any periodic, convergent power series must have coefficients whose inverses grow asymptotically as fast as n! but not faster. I think I can show they most grow faster than O(2n), but that does not prove they are in Θ(n!) unless there is no complexity class between O(2n) and O(n!).

Answer

Hint For exponential you have the growth an+1an=constant

For the factorial you have the growth
bn+1bn=n

Take any function g(n) which grows to infinity slower than n and set
cn+1cn=g(n)

For example, g(n)=n gives the example n! given by AntonioVargas.

Another interesting example is g(n)=ln(n) which gives
dn=nk=2ln(k)

Attribution
Source : Link , Question Author : Robert L. Read , Answer Author : ShreevatsaR

Leave a Comment