-1

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

Allan Jiang
  • 143
  • Fixed that. Is it OK? – Pedro Feb 27 '12 at 02: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. – hmakholm left over Monica Feb 27 '12 at 02: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 02:56
  • Sidenote: you should use "$\cdots \in O(\cdots)$" instead of "$\cdots = O(\cdots)$". –  Feb 27 '12 at 02:57
  • 1
    @J.D. It is like that in my textbook... – Allan Jiang Feb 27 '12 at 03:02
  • @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. –  Feb 27 '12 at 03:16

3 Answers3

3

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.

Matt E
  • 123,735
  • 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 03: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 04:58
  • @Allan: Dear Allan, Jonas Meyer has answered your question very nicely! Regards, – Matt E Feb 27 '12 at 06:40
2

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

Brian M. Scott
  • 616,228
0

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

Jonas Meyer
  • 53,602