Is $\sqrt n = \omega (log^{300}n)$?

Question

When I plug in some really big values of $n$, I find $\sqrt n$ to be much smaller than $(log^{300}n)$. For instance if I plug in $10^{100}$, $\sqrt n = 10^{50}$ and $(log^{300}n) = 4.6 \times 10^{708}$. But the text I was reading states $\sqrt n = \omega (log^{300}n)$. Can someone help me verify this (without taking the limits)?

As I understand if I take $\lim_{x\to\infty}\frac {\sqrt n}{(log^{300}n)}$, we will have to differentiate around $300$ times and finally we will get $\lim_{x\to\infty}{K\times\sqrt n}$ which will give us $\infty$. However I am not sure if I did this correctly. Can someone verify this too?

Answer 1

If you know that $n = \omega(\log n)$, then you are done.

Why? $n^{1/2}=\omega(\log^{300} n)$ is equivalent to $$n^{1/600}=\omega(\log n)\,,\tag{1}$$ and then setting $m=n^{1/600}$ this is in turn equivalent to $$ m = \omega(\log(m^{600}) = \omega(\log m)\tag{2} $$ where we use that $\log(m^{600}) = 600\log(m)$. The last statement (2) is true by assumption, so indeed we are done.

---

Essentially, your issue and doubts are due to the asymptotics. Sure, $\sqrt{n} \leq \log^{300} n$ for any $n$ "big enough": but here $n$ needs to be very big for this to kick in. So trying for small or even reasonable values of $n$ won't help you.

Answer 2

The statement is equivalent to speak $$\lim_{n\to+\infty}\frac{\sqrt n}{(\log n)^{300}}=\lim_{n\to+\infty}\left(\frac{n^{\frac 1 {600}}}{\log n}\right)^{300}=+\infty$$ Since $x\mapsto x^{300}$ is monotonous and continuous, the only thing we need to prove is that $$\lim_{n\to+\infty}\frac{n^{\frac 1 {600}}}{\log n}=+\infty$$ or to say $$n^{\frac 1 {600}}>C\cdot\log n$$ for some $n$ that is large enough and all $C>0$.

This is true if you take the limits. To generate an intuitive example, consider $n=e^{600k}$, then $n^{1/600}-\log n=e^k-600k$. The expression is greater already than $0$ for $k>9$, which means $e^9-9\cdot 600=2703.08\!\ldots$ and $$\sqrt{e^{5400}}\approx 3.93\cdot10^{1172}>5.23\cdot10^{1119}\approx\log^{300}e^{5400}$$.