-1
$\begingroup$

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

  • 0
    Fixed that. Is it OK?2012-02-27
  • 0
    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.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 that2012-02-27
  • 0
    Sidenote: 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 3

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

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.

  • 0
    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!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
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*}$$