Es $\log^2n = O(n)$ o $n = O(\log^2n)$ ¿Es cierto?

Question

Estoy tratando de averiguar si:
1) $\log^2n = O(n)$ y
2) $ n = O(\log^2n)$
son verdaderos o si uno o ambos son falsos.

Hasta ahora he concluido que ambas cosas son falsas porque si $n = 8$ para el primero, y luego $\log^2 8 = O(8)$ lo cual es falso ya que se simplifica a $9 = O(8)$ que no pertenece a $O(n)$ .

Para la segunda, creo que también es falsa porque si $n = 1024$ o (algún otro número grande), se obtiene $1024 = O(\log^2 1024)$ que se simplifica en $1024 = O(100)$ . Y $1024$ no pertenece a $O(100)$ .

¿Estoy en lo cierto o una de estas cosas es cierta? Gracias.

Answer 1

Dado que existe una constante $C$ de manera que, como $n \to \infty$ tenemos $\left|\dfrac{\log^2n}n\right|\leq C$ entonces $\log^2n = O(n)$ .

Pero ya que, como $n \to \infty$ , $\left|\dfrac{n}{\log^2n}\right|\to \infty$ así $n \neq O(\log^2n)$ .

Answer 2

SUGERENCIA:

Para cualquier $\alpha >0$ tenemos $\log n\le \frac{n^{\alpha}}{\alpha}$ . Así, para cualquier $\alpha >0$ tenemos $$\log^2 n\le \frac{n^{2\alpha}}{\alpha^2}$$

Al elegir un $\alpha$ , ¿puede encontrar un número $M$ tal que para $n$ suficientemente grande, tenemos $\log^2 n\le M\,n$ ? De hecho, esta elección para $\alpha$ proporciona un número $M$ que funciona para todos $n\ge 1$ ¡!

Answer 3

Para cualquier exponente $\alpha>0$ , $\;\ln^\alpha n=o(n)$ y a fortiori , $\;\ln^\alpha n=O(n)$ .

$n=O(\ln^2n)$ implicaría $\dfrac{n}{\ln^2n}=O(1)$ es decir. $\; \dfrac{n}{\ln^2n}$ estaría acotado cuando $n\to \infty$ lo que contradice $\ln^2 n=o(n)$ .