Mostrar si $n \sqrt n \in O(n^4)$

Question

Estoy bastante confundido en cuanto a cómo resolver esto paso a paso. Lo que he hecho es graficar esto usando el software de graficación Desmos para verlo visualmente, y puedo ver que el $n \sqrt n $ está por debajo de $n^4$ .

Pensé que podría hacer algo así:

$n \sqrt n \lt n^4$

$ \sqrt n \lt n^3$

$n^{1/2} \lt n^4$

$1 \lt n^4 / n^{1/2}$

$1 \lt n^{7/2}$

Así que basado en esto, $n \sqrt n$ no es bigO de $O(n^4)$ . ¿Es eso correcto? ¿O debería decir que es BigO si $n > 1$ ?

Gracias.

Answer 1

Todo se reduce a $x\ge 1\implies x^2\ge x$ al multiplicar ambos lados por $x$

Para $n\ge 1$

• tienes $\sqrt{n}\ge 1$ así que $n\ge \sqrt{n}$
• también has $n^3\ge n^2\ge n$ por el mismo principio

Reunir todo te da $n^3\ge \sqrt{n}$ que formalmente tiene $n_0=1$ y $C=1$ de la notación Big-O:

$\forall n\ge n_0$ entonces $\sqrt{n}\le Cn^3\iff \sqrt{n}=O(n^3)$

lo que equivale a $n\sqrt{n}=O(n^4)$ como tú mismo has notado.

Answer 2

¿Por qué hacer las cosas más complejas de lo que son? Muy sencillo, $\;n\sqrt n=o(n^4)$ Así que a fortiori Es decir, es $O(n^4)$ .

Dicho esto, ¿cómo se procede desde $\sqrt n < n^3$ a $n^{1/2} < n^4$ ?

Si quiere demostrar directamente que $n\sqrt n=O(n^4)$ (o no), tienes que demostrar la relación $\,\frac{n\sqrt n}{n^4}$ es limitado por alguna constante $C$ para todos $n$ suficientemente grande, y esta constante no es necesariamente $1$ .

Answer 3

${{n\sqrt n}\over n^4}={1\over n^{5/2}}$ y $\lim_\limits{n\rightarrow +\infty}{1\over n^{5/2}}=0$ .