alt Hacker Newslg(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.
My kids love taking about big numbers. TREE(3) is a family favorite. So, I was going over sequences with them, and I decided to go slow instead. My sequence was: 1 1 1 1 ... 1 ...
They accused me of using just "all 1s" (which is, naturally, cheating). Ai contraire!
The count of the number of digits in the decimal representation of the number of unique primes in the prime factorization of the natural numbers.
The best part is that even pretty young kids can compute this sequence; by the first "2" is at 2*3*5*7*11*13*17*19*23*29!
(Hopefully I got that right; the phone doesn't make it easy to type!)