116
$\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$
  • 51
    $\begingroup$ Like $\sqrt{n!}$? $\endgroup$ – Antonio Vargas Jan 8 '18 at 2:09
  • 11
    $\begingroup$ How about $O(n2^n)$? $\endgroup$ – JMoravitz Jan 8 '18 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$ – Alejandro Nasif Salum Jan 8 '18 at 2:12
  • 35
    $\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$ – MathematicsStudent1122 Jan 8 '18 at 2:15
  • 13
    $\begingroup$ $2.00001^n$ is in $O(n!)$ but not in $O(2^n)$. $\endgroup$ – Paulpro Jan 8 '18 at 8:40
190
$\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$
  • 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. Jan 9 '18 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. Jan 9 '18 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. Jan 10 '18 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$ – Mehrdad Jan 10 '18 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. Jan 10 '18 at 4:27
76
$\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$
  • 6
    $\begingroup$ Best answer. It follows that the number of different growth rates between two different growth rates is not bounded. $\endgroup$ – miracle173 Jan 8 '18 at 12:40
  • 5
    $\begingroup$ Nice, but why don't you mention that this is just the geometric mean? $\endgroup$ – leftaroundabout Jan 8 '18 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$ – Iwillnotexist Idonotexist Jan 8 '18 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$ – Geoffrey Brent Jan 8 '18 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 Jan 8 '18 at 23:35
25
$\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$
  • 1
    $\begingroup$ You could abuse some notation and write $O(2^{O(n)})$ :-) $\endgroup$ – yo' Jan 8 '18 at 17:11
  • 7
    $\begingroup$ @yo' The common notation is $3^n = 2^{O(n)}$. $\endgroup$ – Fabio Somenzi Jan 8 '18 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$ – Stella Biderman Jan 9 '18 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$ – Eric Duminil Jan 10 '18 at 10:19
14
$\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$
  • 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 Jan 11 '18 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$ – Especially Lime Jan 11 '18 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 Jan 11 '18 at 15:26
  • $\begingroup$ Constant time is not in the polynomial class I defined above. $\endgroup$ – Especially Lime Jan 11 '18 at 15:50
9
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ true, but this was already stated 7 hours ago here $\endgroup$ – miracle173 Jan 8 '18 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 Jan 8 '18 at 15:27
  • 2
    $\begingroup$ I erroneously introduced this error when I "improved" the latex of his post. $\endgroup$ – miracle173 Jan 8 '18 at 20:37
  • $\begingroup$ This answer looks like a duplicate of Geoffrey Brent's answer. $\endgroup$ – Timothy Jan 11 '18 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$
  • 1
    $\begingroup$ What does this answer add that was not already covered by the others? $\endgroup$ – Antonio Vargas Jan 22 '18 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 Jan 23 '18 at 19:22
  • $\begingroup$ Not to mention N. S.'s answer. $\endgroup$ – Antonio Vargas Jan 23 '18 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.