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.
Which function grows faster: $(n!)!$ or $((n-1)!)!(n-1)!^{n!}$?
7
$\begingroup$
limits
-
0I 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. – 2012-10-09
2 Answers
3
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!)
-
0But 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$ – 2012-10-10
0
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.
-
0That 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... – 2013-09-06