1

How to prove whether the statement is true or not: $$\frac{\sqrt{n}}{\log_2n} = O(n^{1/3})$$?

I know for a fact that the statement is false.

The prove doesn't have to be rigorous, I simply have to convince someone of the validity of the statement.

This is what I tried:

$$\frac{\sqrt{n}}{\log (n)}=n^{(1 / 3)}$$ $$n^{1/2}=n^{(1 / 3)} \log _{2}(n)$$

At this point, I guess it is clear to see that the left side grows faster than the right side. Thus the statement is false.

Now, could I have proved it in some other way?

azif00
  • 20,792
Sebastian Nielsen
  • 612
  • You can check that $$ \frac{\sqrt{n}/\log_n 2}{n^{1/3}} = \frac{n^{1/6}}{\log_2 n} \xrightarrow[n\to\infty]{} \infty. $$ This shows that $\sqrt{n}/\log_n 2 = \mathcal{O}(n^{1/3})$ cannot hold. – Sangchul Lee Sep 28 '19 at 17:35
  • Remember that $\log n$ grows more slowly than any power $n^\alpha$ of $n$ ($\alpha>0$). (This is the equivalent of the observation that any polynomial $P(n)$ grows more slowly than any exponential $a^n$ (for $a>0$).) – Ted Shifrin Sep 28 '19 at 17:43

1 Answers1

1

Suppose that $\frac{\sqrt{n}}{\log_2(n)}=O\!\left(n^{1/3}\right)$. Then there is a $K$ so that $$ \frac{\sqrt{n}}{\log_2(n)}\le Kn^{1/3}\tag1 $$ Then, because $\log(n)\lt n$ for all $n\gt0$, $$ \begin{align} n^{1/6} &\le\frac{K}{\log(2)}\,\log\left(n\right)\\ &=\frac{12K}{\log(2)}\,\log\left(n^{1/12}\right)\\ &\le\frac{12K}{\log(2)}\,n^{1/12}\tag2 \end{align} $$ Inequality $(2)$ implies that $$ n\le\left(\frac{12K}{\log(2)}\right)^{12}\tag3 $$ which cannot be true for all $n$. Contradiction.

Therefore, $\frac{\sqrt{n}}{\log_2(n)}\not\in O\!\left(n^{1/3}\right)$.

robjohn
  • 345,667
  • @SebastianNielsen: to disprove the statement given, I have assumed it true and then arrived at a contradiction. The inequality $(1)$ is simply what follows from assuming $\frac{\sqrt{n}}{\log_2(n)} = O!\left(n^{1/3}\right)$. The inequality you ask about follows directly from $(1)$. – robjohn Sep 28 '19 at 18:28
  • @SebastianNielsen: I have updated my answer to hopefully make things clearer. – robjohn Sep 28 '19 at 18:42