Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true?

Question

I'm trying to figure out if:
1) $\log^2n = O(n)$ and
2) $ n = O(\log^2n)$
are true or if one or both are false.

So far I've concluded that both are false because if $n = 8$ for the first one, then $\log^2 8 = O(8)$ which is false since it simplifies to $9 = O(8)$ which does not belong to $O(n)$.

For the second one, I believe it to be false as well because if $n = 1024$ or (some other big number), you get $1024 = O(\log^2 1024)$ which simplifies to $1024 = O(100)$. And $1024$ does not belong to $O(100)$.

Am I right or is one of these true? Thanks.

Answer 1

Since there exists a constant $C$ such that, as $n \to \infty$, we have $\left|\dfrac{\log^2n}n\right|\leq C$ then $\log^2n = O(n)$.

But since, as $n \to \infty$, $\left|\dfrac{n}{\log^2n}\right|\to \infty$ thus $n \neq O(\log^2n)$.

Answer 2

HINT:

For any $\alpha >0$, we have $\log n\le \frac{n^{\alpha}}{\alpha}$. So, for any $\alpha >0$, we have $$\log^2 n\le \frac{n^{2\alpha}}{\alpha^2}$$

By choosing an $\alpha$, can you find a number $M$ such that for $n$ large enough, we have $\log^2 n\le M\,n$? In fact, this choice for $\alpha$ provides a number $M$ that works for all $n\ge 1$!

Answer 3

For any exponent $\alpha>0$, $\;\ln^\alpha n=o(n)$, and a fortiori, $\;\ln^\alpha n=O(n)$.

$n=O(\ln^2n)$ would imply $\dfrac{n}{\ln^2n}=O(1)$, i. e. $\; \dfrac{n}{\ln^2n}$ would be bounded when $n\to \infty$, whiich contradicts $\ln^2 n=o(n)$.