Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On my homework: prove that $$(\log_2n)^{100} = \mathcal O(n^{1/10})$$ Any ideas are appreciated.

share|improve this question
    
Fixed that. Is it OK? –  Pedro Tamaroff Feb 27 '12 at 2:49
    
Thank you very much! –  Allan Jiang Feb 27 '12 at 2:49
    
One obvious place to start is to unfold the definition of big-O and see where that leads you. Also, the particular constants $100$ and $1/10$ are almost certainly not important for the overall structure of the proof, so wrap them up as symbolic names until you know exactly which calculations to do on them. –  Henning Makholm Feb 27 '12 at 2:52
    
@HenningMakholm I tried to follow the way you said and it led me to O(n) but not O(n^(1/10))... I am not sure how I can approach that –  Allan Jiang Feb 27 '12 at 2:56
1  
@J.D. It is like that in my textbook... –  Allan Jiang Feb 27 '12 at 3:02
show 2 more comments

3 Answers 3

up vote 3 down vote accepted

One possible approach, ugly but straightforward, is to consider the limit of the ratio of $(\log_2n)^{100}$ and $n^{1/10}$ and beat it to death with l’Hospital’s rule:

$$\begin{align*}\lim_{n\to\infty}\frac{(\log_2n)^{100}}{n^{1/10}}&=\lim_{n\to\infty}\frac{100(\ln 2)(\log_2n)^{99}\left(\frac1n\right)}{\frac1{10}n^{-9/10}}\\ &=10\cdot100\cdot(\ln 2)\lim_{n\to\infty}\frac{(\log_2n)^{99}}{n^{1/10}}\\ &=10\cdot100\cdot(\ln 2)\lim_{n\to\infty}\frac{99(\ln 2)(\log_2n)^{98}\left(\frac1n\right)}{\frac1{10}n^{-9/10}}\\ &=10^2\cdot100\cdot99\cdot(\ln 2)^2\lim_{n\to\infty}\frac{(\log_2n)^{98}}{n^{1/10}}\\ &\qquad\qquad\qquad\qquad\vdots\\\\ &=10^{99}\cdot100!\cdot(\ln 2)^{99}\lim_{n\to\infty}\frac{\log_2n}{n^{1/10}}\\ &=10^{100}\cdot100!\cdot(\ln 2)^{100}\lim_{n\to\infty}\frac1{n^{1/10}}\\ &=0\;. \end{align*}$$

share|improve this answer
add comment

Normally, when you have exponents, it is helpful to take logs. So I would suggest taking log of both sides, comparing those, and then seeing what you can say about the original quantities.

share|improve this answer
    
Hi I am not sure about your suggestion. Do you mean I should take log of the O-notation part as well? What will that leads me? Thank you very much! –  Allan Jiang Feb 27 '12 at 3:53
2  
@Allan: You want to show there exists $C>0$ such that $\log(n)^{100}< C n^{1/10}$ for sufficiently large $n$. This is equivalent to $\log\left(\log(n)^{100}\right)<\log\left(C n^{1/10}\right)$. You can use the properties of logs to simplify this inequality and see whether you can find such a $C$. –  Jonas Meyer Feb 27 '12 at 4:58
    
@Allan: Dear Allan, Jonas Meyer has answered your question very nicely! Regards, –  Matt E Feb 27 '12 at 6:40
add comment

If you fix a positive number $p$, can you show that $\log_2 n= O(n^p)$? This can be applied with $p=\frac{1}{1000}$.

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.