Which function grows faster, exponential or factorial? [closed]

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.

Shade

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 ;) – Garrard

wanna see this? – Heartsease

@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. – Shade

@Garrard 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. – Elisha

This question appears to be off-topic because it is about math, not programming. – Calculating

@AlvinWong, How do we make the graph extend beyond x=2? – Underhill

Here's this question with some formulas: math.stackexchange.com/questions/351815/… – Castanets

@PeterMajeed I suppose you're right, but I interpreted it as referring to the running time of algorithms. – Raymonraymond

I'm voting to close this question as off-topic because it has nothing to do with programming. It would be better suited on math.stackexchange.com – Boyar

Answer 1

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.

Genteel

You're correct: math.stackexchange.com/questions/55468/… – Garrard

@Glen, Is there a name for n^n? – Underhill

@Underhill a name for n^n is superexponential – Thebaid

How much faster? :) – Castanets

@Garrard That question doesn't seem to be related. – Raymonraymond

@Glen @Underhill Also relevant, n^n^n...^n is called a power-tower, or tetration (along the same lines as addition, multiplication and exponentiation). So n^n can be said somewhat more trivially as n tetrated by 2. – Knobkerrie

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. – Dupery

Answer 2

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.

Dossier

could not be explained simpler than this. – Checked

same comment as @Checked , i like your simple explanation, simple and powerful :) – Nickel

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

every term of n+1 is larger than n, but it doesn't grow faster :) – Ridley

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. – Dupery

Answer 3

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.

Raymonraymond

Answer 4

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.

Goodtempered

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

>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. – Diadem

good catch, im surprised nobody else commented on it – Goodtempered