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) ?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ One can show $n^\epsilon > \log n$ for any $\epsilon > 0$ provided $n$ is large enough. $\endgroup$– Austin MohrDec 17, 2012 at 1:59
-
$\begingroup$ Thank you. I am convinced of that: $n$ grows much faster than $log n$ clearly. But does that also answer my question ? $\endgroup$– PamDec 17, 2012 at 2:04
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
There is no "largest." Any $\alpha< \dfrac{1}{2}$ is fine, but $\alpha=\dfrac{1}{2}$ is not.
answered Dec 17, 2012 at 2:03
-
$\begingroup$ Thanks 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 ? $\endgroup$– PamDec 17, 2012 at 2:11
-
$\begingroup$ Let $\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$. $\endgroup$ Dec 17, 2012 at 2:14
-
$\begingroup$ Thanks a lot Andre. I get it now. Probably this was also what Austin intended in his reply. Thanks to both of you. Very helpful. $\endgroup$– PamDec 17, 2012 at 2:18
$\begingroup$
$\endgroup$
0
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.
answered Dec 17, 2012 at 2:15