52 cards is the first thing I think of when I think factorials. It's such a great and relatable way to convey the subject to people, plus it usually ends up blowing their minds like it did mine when I first learned of it. Not from this page, but from a YT vid many moons ago.
The main.css file it imports dates itself to March 9 of 2005, and is housed in an "ancient history" section of the website that covers everything before October 26, 2010, so: "sometime between those two years" =P
lg(n!) grows roughly as (n lg n). Constants matter, of course, but to that's the rough estimate.
As an aside, if you take numbers from 0 to (n-1) in an array, there are n! configurations, so representing each configuration or differentiating each configuration take n lg n bits. So, in some sense, taking a mapping that's able to differentiate the input state to map to the ordered state takes at least O(n lg n) time, the standard runtime of a basic sorting algorithm.
Any additional assumptions (n larger than maximum element, distribution of elements) helps reduce this.
Stirling's approximation is also used a lot in statistical mechanics, because you often have to calculate logs of state space sizes, which means lots of combinatorics and thus lots of factorials. Plus it's continuous so you can do calculus.
A quick and dirty approximation of the number of digits in n! is n lg n, which approximates n! from above, via the inequality
1 * 2 * … * n ≤ n * … * n.
(This approximation should be familiar to many from an algorithmics class.)
For a tighter bound, use n lg n - n/2, or a better approximation of ln 10 in place of 1/2 if you wish. This comes from Stirling's approximation which notes that
> (This approximation should be familiar to many from an algorithmics class.)
You need both sides though :)
What makes it interesting for estimating algorithmic complexity is that \log{n!} \in \Theta(n \log n). One side is obvious as you note, the other less so, but there's a famous trick to do both at once:
There is a algorithm call Prime Swing Factorial that can compute large factorials exactly in arbitrary precision math using prime factorization. Like 10000000! in under second depending of how optimized the math library it. Probably like 100x faster than the normal method.
With Lisp you can use iterative algos and get that under a second too.
SBCL can be ridiculously fast; and if you optimize the compilation for integers... the speed gets really close to your solution.
https://czep.net/weblog/52cards.html
Anyone know how to determine the age of this page (it's got be at least 20yrs old)
As an aside, if you take numbers from 0 to (n-1) in an array, there are n! configurations, so representing each configuration or differentiating each configuration take n lg n bits. So, in some sense, taking a mapping that's able to differentiate the input state to map to the ordered state takes at least O(n lg n) time, the standard runtime of a basic sorting algorithm.
Any additional assumptions (n larger than maximum element, distribution of elements) helps reduce this.
For a tighter bound, use n lg n - n/2, or a better approximation of ln 10 in place of 1/2 if you wish. This comes from Stirling's approximation which notes that
You need both sides though :)
What makes it interesting for estimating algorithmic complexity is that \log{n!} \in \Theta(n \log n). One side is obvious as you note, the other less so, but there's a famous trick to do both at once:
\log{n!} = \log{\prod_{h=0}^{n} h} = \sum_{h=0}^{n} \log{h}
Therefore,
\int_0^n \log{x} dx \le \log{n!} \le \int_0^n \log{x+1} dx
with both integrals trivial by parts.