how do you prove that when the limit of n approaches towards positive infinity while n^2/(log n)! We tried to used Stirling theorem but this may not work due to the fact that it may or may not exist on all intervals.
Asked
Active
Viewed 44 times
-1
-
Are you sure this is $(\log n)!$ and not $\log(n!)$ ? – C. Dubussy Feb 08 '16 at 21:45
-
yes, I am 100% for sure that it is (log n)!. I'm trying to show that n^2 is a member of O((log n)!) – Darko Atanackovic Feb 08 '16 at 21:47
-
Is $n$ assumed to be a power of $2$? Otherwise, $\log_2 n$ is not an integer (you can use the $\Gamma$ function instead, in this case, but the factorial as written would not be defined.) – Clement C. Feb 08 '16 at 21:52
1 Answers
1
If $n$ is a power of $2$, write $n=2^k$ and apply Stirling's approximation to $k!$ to show that $$\begin{align} \frac{n^2}{\log^2 n} &= \frac{2^{2k}}{k!} \sim_{n\to\infty} \frac{2^{2k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^k} = \frac{1}{\sqrt{2\pi k}}\cdot \frac{2^{(2+\log e)k}}{2^{k\log k}} = 2^{- k\log k + (2+\log e)k - \frac{1}{2}\log k + O(1) } \\ &= 2^{-k\log k + o(k\log k)}\xrightarrow[n\to\infty]{} 0. \end{align}$$
If $n$ is not a power of two, then $(\log n)!$ should be interpreted as $\Gamma(\log n+1)$. Then use $\Gamma(\log n+1) \geq \Gamma(\lceil \log n \rceil)$ (the $\Gamma$ function is increasing) and do the above for $k = \lceil \log n \rceil$.
Clement C.
- 67,323
-
Just curious, and not that it changes the development, but why have you assumed base $2$ for the logarithm? – Mark Viola Feb 08 '16 at 22:18
-
-
-
-
so for 2^(−klogk+o(klogk)), how do we know that o(klogk) approaches zero? – Darko Atanackovic Feb 08 '16 at 22:36
-
$- k\log k + o(k\log k) \xrightarrow[k\to\infty]{} -\infty$, since the first term dominates and goes to $-\infty$. So $2^{- k\log k + o(k\log k)} \xrightarrow[k\to\infty]{} "2^{-\infty}" = 0$. – Clement C. Feb 08 '16 at 22:37