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

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?

• Do you mean to say that even for a huge value like $n=e^{600}$, the ratio is extremely small, so we need really really humongous value of $n$ to make the ratio tend to infinity? Mar 11, 2018 at 15:20
• I was being silly. Yes we need to go even bigger.
– anon
Mar 11, 2018 at 19:43
• After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark ✓ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?. Mar 12, 2018 at 20:56

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