4 ms·

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_approx

• madcaptenor 11y ago
  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.)
  • ph0rque 11y ago
    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).