# Prove $(\log_2n)^{100} = \mathcal O(n^{1/10})$

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

-
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
@J.D. It is like that in my textbook... –  Allan Jiang Feb 27 '12 at 3:02

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*}

-

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.

-
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
@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

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}$.

-