On my homework: prove that $$(\log_2n)^{100} = \mathcal O(n^{1/10})$$ Any ideas are appreciated.
Prove $(\log_2n)^{100} = \mathcal O(n^{1/10})$
-
0Fixed that. Is it OK? – 2012-02-27
-
0One 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. – 2012-02-27
-
0@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 – 2012-02-27
-
0Sidenote: you should use "$\cdots \in O(\cdots)$" instead of "$\cdots = O(\cdots)$". – 2012-02-27
-
1@J.D. It is like that in my textbook... – 2012-02-27
-
0@AllanJiang Check out this https://rniwa.com/2011-08-20/big-o-n1-01-and-nlog-n2/ I think you should be able to use the theorem. – 2012-02-27
3 Answers
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}$.
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.
-
0Hi 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! – 2012-02-27
-
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$. – 2012-02-27
-
0@Allan: Dear Allan, Jonas Meyer has answered your question very nicely! Regards, – 2012-02-27
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*}$$