Hacker News Reader

Comment by jfoutz | Hacker News Reader

Huh. I always thought n! grew faster than c^n which would be even worse than exponential. Maybe enough cancels out to make it simpler than it appears.

edit

Actually, for even dimensions it's pretty clear. n = dimension/2

    pi^n / n!

factorial wins. The problem is worse than exponentiation.

View on HN

At some point, I wondered if n! is proportional to n^n.

Turns out, it is:

n! ~= (2 * pi * n)^1/2 * (n/e)^n

(https://en.wikipedia.org/wiki/Stirling%27s_approximation)

Not exactly "proportional", because you have that pesky e in the denominator. But that's the right idea. Basically, to get n! you're multiplying together n things that are sort of n-ish, so you'd expect n! ~ n^n. (When the numbers get really big, like in statistical mechanics, I've seen the approximation log n! ~ n log n.) The next step is to figure that you're multiplying together n things that are on average n/2, so n! ~ (n/2)^n. But then it really turns out that you should have been using a geometric average (since you're multiplying), not an arithmetic one, so n! must be smaller yet. (I don't know a way to get (n/e)^n without doing an integral, though.)

Right, proportional in the sense that for both n! and n^n, the fastest-growing component is ~n^n. (I was curious in the context of which grew faster for larger values of n in the big O notation).

But if you have r=sqrt(n) that works out fine.

Reply on news.ycombinator.com