129
$\begingroup$

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

$\endgroup$
11
  • 56
    $\begingroup$ Like $\sqrt{n!}$? $\endgroup$ Commented Jan 8, 2018 at 2:09
  • 12
    $\begingroup$ How about $O(n2^n)$? $\endgroup$
    – JMoravitz
    Commented Jan 8, 2018 at 2:09
  • 6
    $\begingroup$ Well, $j(n)=a^n$ for $a>2$ works, but maybe you're actually interested in a function between $a^n$ and $n!$ for every $a \in \mathbb R$. $\endgroup$ Commented Jan 8, 2018 at 2:12
  • 37
    $\begingroup$ A standard result says that $n!$ is asymptotically equivalent to $$\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$ With this in mind, it's rather easy to come up with examples. $\endgroup$ Commented Jan 8, 2018 at 2:15
  • 15
    $\begingroup$ $2.00001^n$ is in $O(n!)$ but not in $O(2^n)$. $\endgroup$
    – Paul
    Commented Jan 8, 2018 at 8:40

7 Answers 7

206
$\begingroup$

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

$\endgroup$
12
  • 2
    $\begingroup$ @Mehrdad $\ln(d_n) = \sum_{k=2}^n \ln ( \ln (k))$. So the "natural" continuous analog should be $$\ln(f(x)) =\int_2^x \ln( \ln(t)) dt$$ or$$f(x)=e^{\int_2^x \ln( \ln(t)) dt}$$ $\endgroup$
    – N. S.
    Commented Jan 9, 2018 at 20:09
  • 1
    $\begingroup$ @Mehrdad Note that i am looking at the rate of growth, not at the value at some point, so when I say $f(x)=e^{\int_2^x \ln( \ln(t)) dt}$, if you want to start at a certain value, you should look at $f(x)=C e^{\int_2^x \ln( \ln(t)) dt}$ instead. $\endgroup$
    – N. S.
    Commented Jan 9, 2018 at 23:04
  • 1
    $\begingroup$ @Mehrdad If you want a continuous function such that $f(n+1)/f(n)=\frac{d_{n+1}}{d_n}$ that can be achieved in uncountably many ways (since you are just asking for continuous function which takes certain values on the integers), but IMO those are artificial. $\endgroup$
    – N. S.
    Commented Jan 10, 2018 at 4:22
  • 1
    $\begingroup$ Ohh, I see, okay thanks. That's definitely not what I meant by continuous though haha. :-) (I haven't even seen people view it that way at all, so this is my first time.) I meant in the same sense that the gamma function is the continuous analog of a factorial -- i.e., giving the same results, but being defined over the reals rather than the integers, and satisfying some desirable regularity conditions (to make it unique as you just mentioned). $\endgroup$
    – user541686
    Commented Jan 10, 2018 at 4:22
  • 1
    $\begingroup$ @Mehrdad In that sense I don't know any. But it is interesting that if we replace $\prod$ in the definition of $d_n$ with $\sum$ you actually get $\ln(n!)$ :) $\endgroup$
    – N. S.
    Commented Jan 10, 2018 at 4:27
86
$\begingroup$

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.

$\endgroup$
10
  • 8
    $\begingroup$ Best answer. It follows that the number of different growth rates between two different growth rates is not bounded. $\endgroup$
    – miracle173
    Commented Jan 8, 2018 at 12:40
  • 5
    $\begingroup$ Nice, but why don't you mention that this is just the geometric mean? $\endgroup$ Commented Jan 8, 2018 at 16:53
  • 3
    $\begingroup$ @leftaroundabout Because any $j(x) = f^p(x) g^q(x)$ with $p, q \in \mathbb{R}^+, \; p+q=1$ and $f, g$ as stated by OP would satisfy his request of growing faster than exponential but slower than factorial, and so there are uncountably many examples. The geomean is just the special case $p=q=0.5$. $\endgroup$ Commented Jan 8, 2018 at 20:55
  • 1
    $\begingroup$ @leftaroundabout You're welcome to mention it! I just didn't think the name added much to the answer, but YMMV. $\endgroup$
    – G_B
    Commented Jan 8, 2018 at 23:01
  • 1
    $\begingroup$ I agree that it doesn't seem particularly important to mention that this is the geometric mean (although it certainly wouldn't hurt if you chose to do so). $\endgroup$
    – David Z
    Commented Jan 8, 2018 at 23:35
26
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ You could abuse some notation and write $O(2^{O(n)})$ :-) $\endgroup$
    – yo'
    Commented Jan 8, 2018 at 17:11
  • 7
    $\begingroup$ @yo' The common notation is $3^n = 2^{O(n)}$. $\endgroup$ Commented Jan 8, 2018 at 18:35
  • 3
    $\begingroup$ This is an excellent and under appreciated answer. I challenge any reader to estimate how far apart $O(n!)$ and $O((n/2)!)$ are. You’re almost certain to underestimate it massively. $\endgroup$ Commented Jan 9, 2018 at 3:43
  • 4
    $\begingroup$ @StellaBiderman: What do you mean "estimate"? Between bazillions and $\prod_{i=n/2+1}^{n} i$, I'm not sure which answer you expect. $\endgroup$ Commented Jan 10, 2018 at 10:19
16
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Logarithms having the same growth is sufficient to put exponentials all into a single complexity class, because logarithm is the anti-function of an exponent. Logarithm is not the anti-function of factorial, so it does not follow that the family you've defined as "factorial-like" fall into a single complexity class. $\endgroup$
    – Ben Voigt
    Commented Jan 11, 2018 at 0:54
  • 1
    $\begingroup$ @BenVoigt I think the fact that logarithms happen to be inverses of exponentials is a red herring here. I am simply defining my complexity classes based on $f(n)$ being in the same class as $g(n)$ if $\log(f(n))=\Theta(\log(g(n))$. This notion is the natural one to use to define not only the exponential class $\log(f(n))=\Theta(n)$ but also the polynomial class $\log(f(n))=\Theta(\log n)$. $\endgroup$ Commented Jan 11, 2018 at 10:41
  • $\begingroup$ But we normally don't put all polynomials in the same class -- at least constant time and linear time receive separate classes. $\endgroup$
    – Ben Voigt
    Commented Jan 11, 2018 at 15:26
  • $\begingroup$ Constant time is not in the polynomial class I defined above. $\endgroup$ Commented Jan 11, 2018 at 15:50
9
$\begingroup$

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

$\endgroup$
4
  • 6
    $\begingroup$ true, but this was already stated 7 hours ago here $\endgroup$
    – miracle173
    Commented Jan 8, 2018 at 12:42
  • 6
    $\begingroup$ Right, I didn't realize it because he wrote $j = \sqrt{\frac{f}{g}}$ instead of $j = \sqrt{fg}$ which I assume must be a typo? $\endgroup$
    – Rchn
    Commented Jan 8, 2018 at 15:27
  • 2
    $\begingroup$ I erroneously introduced this error when I "improved" the latex of his post. $\endgroup$
    – miracle173
    Commented Jan 8, 2018 at 20:37
  • $\begingroup$ This answer looks like a duplicate of Geoffrey Brent's answer. $\endgroup$
    – Timothy
    Commented Jan 11, 2018 at 20:13
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ What does this answer add that was not already covered by the others? $\endgroup$ Commented Jan 22, 2018 at 23:03
  • $\begingroup$ I thought I had read all the answers carefully. Now I see that Especially Lime's answer also answers the question though it might be harder to understand the proof in that answer than in mine. $\endgroup$
    – Timothy
    Commented Jan 23, 2018 at 19:22
  • $\begingroup$ Not to mention N. S.'s answer. $\endgroup$ Commented Jan 23, 2018 at 20:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .