0

Is the following statement true or false?

$(\log n)^{10} = O(n^{0.10})$

When trying to solve this, I thought it was false, but according to my teacher's answers, it's true.

I would like to know if there is a quick and easy way to solve exercises like this?

Batman
  • 19,390
Jesper
  • 121
  • I have no idea how to write exponents correctly and Google's answer was wrong, apparently. – Jesper Jun 02 '16 at 22:24
  • Sometimes it pays to simplify the comparison. By definition the claim being made is that as $n$ tends to infinity (?!), the ratio of $(\log n)^{10}$ to $n^{0.1}$ is bounded. Think about whether we can work instead with the tenth root of both numerator and denominator, showing that simplified ratio is bounded. – hardmath Jun 02 '16 at 22:25
  • You'd probably like to bookmark the Basic Tutorial and Quick Reference for posting mathematical expressions and related notational matters. – hardmath Jun 02 '16 at 22:33

1 Answers1

1

Any power of logarithm grows slower than any positive power of $n$. If you look at the limit of $\frac{\log ((\log n)^k)}{\log ( n^p)} = \frac{ k \log \log n}{p \log n} \to 0$ since $\log \log n / \log n \to 0$ for any $k,p$. So, there exists a $N$ such tat for all $n \geq N$, $(\log n)^{10} \leq n^{0.10}$ (else the limit described prior would be a constant or tending to infinity).

Batman
  • 19,390
  • Using my exact example, how could I show that $O(n^{0.10})$ grows faster? It always seems to have less growth than the other one when I try to calculate it using random numbers, but that might be the wrong way to check it. – Jesper Jun 03 '16 at 00:03
  • Let $n=e^{1000}$. On the left we have $1000^{10}$, on the right $e^{100}$, which is bigger by quite a bit, since $e^{10}\gt 2^{10}\gt 1000$. It is not hard to show that the LHS is less than the RHS past $n=e^{1000}$. We don't need to go all the way to $e^{1000}$, but we do have to go out a very long way, which accounts for the fact that numerical experimentation did not succeed. – André Nicolas Jun 03 '16 at 00:40