3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – shiva
    Mar 11, 2018 at 15:20
  • $\begingroup$ I was being silly. Yes we need to go even bigger. $\endgroup$
    – anon
    Mar 11, 2018 at 19:43
  • $\begingroup$ 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?. $\endgroup$
    – Clement C.
    Mar 12, 2018 at 20:56

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.