# Which function grows faster: $(n!)!$ or $((n-1)!)!(n-1)!^{n!}$?

Of course, I can use Stirling's approximation, but for me it is quite interesting, that, if we define $k = (n-1)!$, then the left function will be $(nk)!$, and the right one will be $k! k^{n!}$. I don't think that it is a coincidence. It seems, that there should be smarter solution for this, other than Stirling's approximation.

-
You don't think "what" is a coincidence? –  Graphth Oct 9 '12 at 14:09
I cannot explicitely explain why did I say so. Probably, I just wanted to point that it seems that there should be smarter solution others than Stirling's approximation. But, of course, I can be wrong. –  Kos Oct 9 '12 at 14:22

For $(nk)!$ your factors are $1,2,3,\dots, k$ then $k+1, \dots, 2k,2k+1 \dots, k!$.

For $k! k^{n!}$ your factors are $1,2,3,\dots, k$ but then constant $k,\dots,k$.

So every factor of (nk)! is > or = to each factor of k!k^(n!)

-
You can use \geq for $\geq$ –  The Chaz 2.0 Oct 9 '12 at 17:05
But total numher of factors in the first function is $n!$, while in the second it is $k+n!$, so it has extra $k$ factors, each equals to $k$ –  Kos Oct 10 '12 at 7:24

Take $\log$ on both sides and use the $\log {n!} = \Theta(n\log n)$. The first terms becomes $\Theta(n!\log{(n!)})$, the second one becomes $\Theta((n-1)!\log {(n-1)!}) + \Theta(n!\log{(n-1)!})$. So it's obvious that the first terms grows faster than the second one.

-
It might be useful to expand on this answer a little bit. In particular, it's not immediately clear to me why there's an asymptotic gap between $n! log(n!)$ and $n! \log((n-1)!)$. –  Micah Sep 5 '13 at 21:05
$n!\log(n!) - n!\log{(n-1)!} = n!(\log{n!} - \log{(n-1)!}) = n!(\log{n})$ –  platinor Sep 6 '13 at 21:10
That looks an awful lot like a proof that $n! log(n!)$ is $\Theta(n!(\log(n-1)!))$ to me (since $n! \log n$ grows more slowly than either of the other two terms). It looks to me like you need sharper asymptotics than $\Theta$-notation gives you, which leads back towards Stirling's approximation... –  Micah Sep 6 '13 at 21:26