Is $n^\frac{1}{10} \in O((\log n)^{10})$?

Question

This question came up in a recent discussion: is $n^\frac{1}{10} \in O((\log n)^{10})$?

First time I've come across a power of a log in a long time, and as far as I recall, there are no identities for power of logs. Not sure how tackle this.

Answer 1

Hint: $$ \frac{n^{1/10}}{(\log n)^{10}} = \left(\frac{n^{1/100}}{\log n} \right)^{10} $$

Answer 2

Comparing $f(n)=n^{1/10}$ and $g(n)=(\log n)^{10}$ may be done more informally by studying what happens when you square $n$: $f$ is squared, while $g$ is multiplied by $1024$. Clearly $f$ will eventually overtake any constant multiple of $g$ by repeatedly squaring the argument.

Answer 3

From the usual limit $\dfrac{\log n}{n} \mathop{\longrightarrow}\limits_{n \rightarrow +\infty} 0$ you can get $\dfrac{(\log n)^a}{n^b} \mathop{\longrightarrow}\limits_{n \rightarrow +\infty} 0$ for any $a > 0$ and $b > 0$.

So you don't have $n^\frac{1}{10} \in O((\log(n)^{10})$ but on the contrary $(\log n)^{10} \in O(n^\frac{1}{10})$.