What is the largest exponent $\alpha$ such that the ratio between $ n^{\alpha}$ and $ (\sqrt{n} / \log{ \sqrt n}) $ still remains asymptotically bounded (can assume $n$ positive integer) ?
Simple question about asymptotics of a ratio
3
$\begingroup$
functions
asymptotics
-
0One can show $n^\epsilon > \log n$ for any $\epsilon > 0$ provided $n$ is large enough. – 2012-12-17
-
0Thank you. I am convinced of that: $n$ grows much faster than $log n$ clearly. But does that also answer my question ? – 2012-12-17
2 Answers
3
There is no "largest." Any $\alpha< \dfrac{1}{2}$ is fine, but $\alpha=\dfrac{1}{2}$ is not.
-
0Thanks Andre, very interesting, this would corresponds to my "intuition" too. What could be a simple argument to justify that ? Clearly, after 1/2 the logarithm causes a "runaway to infinity". Why below 1/2 it sufficies to keep the ratio bounded ? – 2012-12-17
-
0Let $\alpha=\frac{1}{2}-\epsilon$, where $\epsilon$ is positive. A little algebra brings us to $\dfrac{\log(\sqrt{n})}{n^\epsilon}$. This has limit $0$ as $n\to\infty$, say by L'Hospital's Rule. One can make the calculation easier by saying that $\log(\sqrt{n})=(1/2)\log n$. – 2012-12-17
-
0Thanks a lot Andre. I get it now. Probably this was also what Austin intended in his reply. Thanks to both of you. Very helpful. – 2012-12-17
2
The ratio in question can be simplified to $$\frac{n^\alpha}{\sqrt n / \log\sqrt n} = n^{\alpha-\frac12} \log\sqrt n.$$ So, when is this asymptotically bounded? Clearly if $\alpha \geq \frac12$ then the first term is strictly positive and nondecreasing, and the second term is increasing without bound, so the entire thing is unbounded. If $\alpha < \frac12$ then the first term will decrease faster than the second term increases (for the reason Austin Mohr notes), so the product will be bounded.