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

  • 0
    Thank 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 2

3

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

  • 0
    Than$k$s 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.