Which function grows faster, exponential or factorial?

Question

Which function grows faster, exponential (like 2^n, n^n, e^n etc) or factorial (n!)? Ps: I just read somewhere, n! grows faster than 2^n.

Q: Why don't you try it? With a program, or simply look at a series of a few numbers? You'll find the answer in less time than it took to ask this question ;) — paulsm4, Jul 23 '12 at 06:27
wanna see [this](http://www.wolframalpha.com/input/?i=y%3D2%5Ex%2C+y%3Dx%5E2%2C+y%3Dx%21)? — Alvin Wong, Jul 23 '12 at 06:43
@paulsm4, I already tried with simple excel. But, unfortunately I couldn't go more than 144 (ie., 144^144) due to overflow. Hence I thought to ask some theoretical proof for the same. — devsathish, Jul 23 '12 at 06:56
@paulsm4 It's not so simple as just trying it. Curves can be deceptive. The result depends on the coefficient, and the crossover point may be difficult to find. — Dan Nissenbaum, Mar 27 '13 at 15:36
This question appears to be off-topic because it is about math, not programming. — Peter Majeed, May 14 '14 at 15:34
Here's this question with some formulas: https://math.stackexchange.com/questions/351815/do-factorials-really-grow-faster-than-exponential-functions — Vytenis Bivainis, Apr 30 '18 at 22:03
@PeterMajeed I suppose you're right, but I interpreted it as referring to the running time of algorithms. — inavda, Mar 23 '19 at 20:47
I'm voting to close this question as off-topic because it has nothing to do with programming. It would be better suited on https://math.stackexchange.com/ — Dharman, Feb 17 '20 at 21:46

score 181 · Accepted Answer · answered Jul 23 '12 at 06:38

181

n! eventually grows faster than an exponential with a constant base (2^n and e^n), but n^n grows faster than n! since the base grows as n increases.

answered Jul 23 '12 at 06:38

Glen Hughes

4,712
2
20
25

3

You're correct: http://math.stackexchange.com/questions/55468/how-to-prove-that-exponential-grows-faster-than-polynomial – paulsm4 Jul 23 '12 at 20:27
34

@Glen, Is there a name for `n^n`? – Pacerier Jun 26 '14 at 17:37
30

@Pacerier a name for n^n is superexponential – dklovedoctor Apr 26 '17 at 04:23
2

How much faster? :) – Vytenis Bivainis Apr 30 '18 at 22:01
1

@paulsm4 That question doesn't seem to be related. – inavda Mar 22 '19 at 14:20
3

@Glen @Pacerier Also relevant, `n^n^n...^n` is called a power-tower, or [tetration](https://en.wikipedia.org/wiki/Tetration) ([along the same lines as addition, multiplication and exponentiation](https://en.wikipedia.org/wiki/Hyperoperation)). So `n^n` can be said somewhat more trivially as `n` _tetrated by_ 2. – Ben J Jul 16 '20 at 06:04
In fact, n! grows asymptotically exactly like n^n, as seen by Sterling's formula: $n! \simeq \sqrt{2\pi n} (n/e)^n$. Both are superexponential, as no exponential with a constant base can grow this fast. – James Oct 18 '22 at 11:12

score 132 · Answer 2 · answered Mar 17 '16 at 15:16

132

n! = n * (n-1) * (n-2) * ...

n^n = n * n * n * ...

Every term after the first one in n^n is larger, so n^n will grow faster.

answered Mar 17 '16 at 15:16

AlexQueue

6,353
5
35
44

18

could not be explained simpler than this. – sn.anurag Apr 01 '19 at 04:36
same comment as @sn.anurag , i like your simple explanation, simple and powerful :) – ibra Sep 28 '20 at 15:48
1

This answer is useful, but it could be improved by doing something similar to compare `n!` and `2^n` (and that reasoning would extend to any constant base). – Bernhard Barker Jul 25 '21 at 15:01
2

every term of `n+1` is larger than `n`, but it doesn't grow faster :) – Voskanyan David Oct 06 '21 at 07:02
This is not quite right. Yes, n^n is larger than n!, but that's not usually what we mean when we talk about growth rates. By Sterling's formula, n! and n^n are asymptotically equivalent up to a constant scaling: n! approaches \sqrt{2\pi n} (n/e)^n as n grows. – James Oct 18 '22 at 11:14

inavda · Answer 3 · 2019-10-06T22:41:07.597

n^n grows larger than n! -- for an excellent explanation, see the answer by @AlexQueue.

For the other cases, read on:

Factorial functions do asymptotically grow larger than exponential functions, but it isn't immediately clear when the difference begins. For example, for n=5 and k=10, the factorial 5!=120 is still smaller than 10^5=10000. To find when factorial functions begin to grow larger, we have to do some quick mathematical analysis.

We use Stirling's formula and basic logarithm manipulation:

log_k(n!) ~ n*log_k(n) - n*log_k(e)

k^n = n!
log_k(k^n) = log_k(n!)
n*log_k(k) = log_k(n!)
n = log_k(n!)

n ~ n*log_k(n) - n*log_k(e)
1 ~ log_k(n) - log_k(e)
log_k(n) - log_k(e) - 1 ~ 0
log_k(n) - log_k(e) - log_k(k) ~ 0
log_k(n/(e*k)) ~ 0

n/(e*k) ~ 1
n ~ e*k

Thus, once n reaches almost 3 times the size of k, factorial functions will begin to grow larger than exponential functions. For most real-world scenarios, we will be using large values of n and small values of k, so in practice, we can assume that factorial functions are strictly larger than exponential functions.

Frontear · Answer 4 · 2022-09-10T01:52:22.713

I want to show you a more graphical method to very easily prove this. We're going to use division to graph a function, and it will show us this very easily.

Let's use a basic and boring division function to explain a property of division.

As a increases, the evaluation of that expression also increases. As a decreases, the evaluation of that expression also decreases.

Using this idea, we can plot a graph based on what we expect to increase, and expect to decrease, and make a comparision as to which increases faster.

In our case, we want to know whether exponential functions will grow faster than factorials, or vice versa. We have two cases, a constant to a variable exponent vs. a variable factorial, and a variable to a variable exponent vs a variable factorial.

Graphing these tools with Desmos (no affiliation, it's just a nice tool), shows us this:

Graph of a constant to variable exponent, vs variable factorial

Although it initially seems that the exponential expression increases faster, it hits a point where it no longer increases as fast, and instead, the factorial expression is increasing faster.

Graph of a variable to variable exponent, vs variable factorial

Although it initially seems to be slower, it begins to rise rapidly past that point, therefore we can conclude that the exponential must be increasing faster than the factorial.

Note: `a/b` will tend to infinity if `a` grows faster than `b` and it will tend to `0` if `b` grows faster than `a` (and it will tend to a constant if they grow at the same rate). — Bernhard Barker, Jul 25 '21 at 15:04
>As b decreases, the evaluation of that expression also decreases. This is a false statement. As b decreases, the evaluation of the expression increases. Aside from that I like the explanation. — DudeGuy, Aug 29 '22 at 23:46

Which function grows faster, exponential or factorial?

4 Answers4

Graph of a constant to variable exponent, vs variable factorial

Graph of a variable to variable exponent, vs variable factorial