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

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.)

Answer 5

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

Answer 6

To add to Especially Lime's answer, there are a couple of common kinds of classes of asymptotic behaviour relative to any given class. As $n \overset{\in\mathbb{N}}\to \infty$, we often naturally encounter not just $O(f(n))$ but also $f(n)^{O(1)}$ and $f(n)^{o(1)}$. (For definition of $o(1)$ see Landau notation.) And there are still asymptotic growth rates between $\log\log(n)^{Θ(1)}$ and $\log(n)^{Θ(1)}$, such as $(\log\log(n))^{\log\log\log(n)}$.

Answer 7

I know of many exponential functions but only one factorial function. The title means "is there a function that grows asymptotically faster than all exponential functions and slower than the factorial function" but the body asks whether there is a function that grows faster than the function $f(x) = 2^x$ and slower than $f(x) = x!$ so I will give an answer that answers both questions. It's obvious that if the answer to the first question is yes then so is the answer to the second question so I will just prove that the answer to the first question is yes. I will show that $f(x) = \sqrt(x!)$ grows asymptotically faster than all exponential functions and slower than $x!$. Every real exponential function with domain $R$ is of the form $a \times b^x$ where $b$ is a positive real number but when $b$ is 0 or negative, the domain is not all of $R$. Suppose for some real numbers $a$ and $b$, $g(x) = a \times b^x$ for all "$x$ where $a \times b^x$ is defined. For integers more than the floor function of $b^2$ the factorial function grows more rapidly than $g(x) = a \times b^x$. Therefore, the factorial function grows asymptotically faster than all exponential functions.