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

Question

In big-O notation the complexity class $O(2^n)$ is named "exponential". The complexity class $O(n!)$ is named "factorial".

I believe that $f(n) = O(2^n)$ and $g(n) = O(n!)$ means that $\dfrac{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(2^n)$, such that: $$ (j(n) \neq O(2^n)) \wedge (j(n) = O(n!)) \wedge (n! \neq O(j(n))) $$ or, informally, $j(n)$ grows asymptotically strictly faster than $2^n$ 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(2^n)$, but that does not prove they are in $\Theta(n!)$ unless there is no complexity class between $O(2^n)$ and $O(n!)$.

Answer 1

Hint For exponential you have the growth $$\frac{a_{n+1}}{a_n}=\mbox{constant}$$

For the factorial you have the growth $$\frac{b_{n+1}}{b_n}=n$$

Take any function $g(n)$ which grows to infinity slower than $n$ and set $$\frac{c_{n+1}}{c_n}=g(n)$$

For example, $g(n)=\sqrt{n}$ gives the example $\sqrt{n!}$ given by AntonioVargas.

Another interesting example is $g(n)=\ln(n)$ which gives $$d_n =\prod_{k=2}^n \ln(k)$$

Answer 2

Given any two positive functions $f$ and $g$ such that $\frac{f(x)}{g(x)}$ tends to zero, let $j(x) = \sqrt{f(x)g(x)}$ (this is the geometric mean of $f$ and $g$).

Then $\frac{f}{ j} = \frac{j}{ g} = \sqrt{\frac{f}{g}}$ which must also tend to zero, so $j$ is an intermediate complexity class.

Answer 3

For variety, here are two striking examples of such a $j$ that demonstrate just how narrow the big-theta complexity classes are when applied to such rapidly growing functions:

• $j(n) = 3^n$
• $j(n) = (n-1)!$

The first demonstrates something you may have misunderstood: exponential growth is a much wider complexity class than merely $O(2^n)$.

Answer 4

For any functions $f$ and $g$, $\sqrt{fg}$ has a growth that's between $f$ and $g$.

Answer 5

A lot of the answers given are actually "like" factorial: if you lump all the exponential-growth functions into a single class, it would make sense to lump things like $n!$ and $\sqrt{n!}$ in a single class too. But there are still classes in between.

What do I mean by this? Functions like $2^n$ and $3^n$ are really not very similar if you compare them directly - $3^n$ grows much much faster and isn't close to being $O(2^n)$. But what makes them similar is that their logarithms have the same growth - $\log(2^n)=\Theta(\log(3^n))=\Theta(n)$.

Now $\log(n!)=\Theta(n\log n)$, and so it would make sense to put all functions with this property - such as $\sqrt{n!}$ or $(n/2)!$ or $n^n$ - into a general "factorial" class in the same way as we define the exponential class.

With this way of thinking, it's clear that there is still something in between, which grows faster than anything exponential-like but slower than anything factorial-like. You just need to pick some function $f(n)$ which grows faster than $\Theta(n)$, but slower than $\Theta(n\log n)$, such as $f(n)=n\sqrt{\log n}$ or $f(n)=n\log\log n$, and then $\exp(f(n))$ is in an intermediate class.

The second choice I suggested for $f(n)$ gives you something quite natural: $\exp(n\log\log n)=(\log n)^n$. (This is the same type of function as N.S.'s second example above.)