Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am trying to find out why $(\log(n))^{99} = o(n^{\frac{1}{99}})$. I tried to find the limit as this fraction goes to zero.

$$ \lim_{n \to \infty} \frac{ (\log(n))^{99} }{n^{\frac{1}{99}}} $$

But I'm not sure how I can reduce this expression.

share|improve this question
1  
What have you tried? –  Raphael Feb 17 '13 at 9:15
add comment

3 Answers 3

up vote 6 down vote accepted

$\qquad \begin{align} \lim_{x \to \infty} \frac{ (\log(x))^{99} }{x^{\frac{1}{99}}} &= \lim_{x \to \infty} \frac{ (99^2)(\log(x))^{98} }{x^{\frac{1}{99}}} \\ &= \lim_{x \to \infty} \frac{ (99^3) \times 98(\log(x))^{97} }{x^{\frac{1}{99}}} \\ &\vdots \\ &= \lim_{x \to \infty} \frac{ (99^{99})\times 99! }{x^{\frac{1}{99}}} \\ &= 0 \end{align}$

I used L'Hôpital's rule law in each conversion assuming natural logarithm.

share|improve this answer
    
Important to note: this works because $99$ is finite; I have seen people hide $n$ applications of L'Hôpital in $\dots$. Also, be very wary of using the rule in the context of discrete functions; I have seen people (trying to) apply it to $n!$. –  Raphael Feb 17 '13 at 8:56
1  
Please consider not reinforcing behaviour that hurts the site. –  Raphael Feb 17 '13 at 10:18
    
@Raphael: I think in the case of $n!$, $\Gamma(x)$ or Stirling's approximation could be used to make it suitable for applying L'Hôpital for large $n$. –  Reza Feb 17 '13 at 23:42
    
Go ahead and try; not only is the derivation of $\Gamma$ even harder to handle, but it is clear that L'Hôpital can not help for exponential functions: the derivations are (at least) as hard as the original functions. Stirling's formula, on the other hand, is usually a good idea. See also my answer over here. –  Raphael Feb 18 '13 at 8:46
add comment

Hint: take $99$th root of both sides.

share|improve this answer
add comment

Try a common trick: express both functions as $e^{\dots}$ and compare the exponents; if their ratio tends to $0$ or $\infty$, so does the original quotient (see here for the full rule).

$\frac{(\log n)^{99}}{n^{\frac{1}{99}}} = \frac{e^{99 \cdot \log(\log n)}}{e^{\frac{1}{99} \cdot \log n}}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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