-1
$\begingroup$

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

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