3
$\begingroup$

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) ?

$\endgroup$
2
  • $\begingroup$ One can show $n^\epsilon > \log n$ for any $\epsilon > 0$ provided $n$ is large enough. $\endgroup$ Dec 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$
    – Pam
    Dec 17, 2012 at 2:04

2 Answers 2

3
$\begingroup$

There is no "largest." Any $\alpha< \dfrac{1}{2}$ is fine, but $\alpha=\dfrac{1}{2}$ is not.

$\endgroup$
3
  • $\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$
    – Pam
    Dec 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$
    – Pam
    Dec 17, 2012 at 2:18
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.