[Euclides]

Hola, demostre esta proposición a ver si era verdadera o falsa del análisis asintótico, pueden revisarla?

Determine si \( f(n)\in{O(f(n)^2)} \) es verdadera:
Es falsa, veamos porqué:
de la regla del producto vemos que:
Si \( f(n)\in{O(f(n))} \) y \( 1\in{O(f(n))}\Longrightarrow{ f(n)\in{O(f(n)^2)}} \)
La primera de las primeras es evidentemente cierta, mietras que la segunta es cierta si y solo si \( f(n)=1 \) pero esto implica que no es para toda \( f(n) \), por tanto la proposión es falsa

[Luis Fuentes]

Hola, demostre esta proposición a ver si era verdadera o falsa del análisis asintótico, pueden revisarla?

Determine si \( f(n)\in{O(f(n)^2)} \) es verdadera:
Es falsa, veamos porqué:
de la regla del producto vemos que:
Si \( f(n)\in{O(f(n))} \) y \( 1\in{O(f(n))}\Longrightarrow{ f(n)\in{O(f(n)^2)}} \)
La primera de las primeras es evidentemente cierta, mietras que la segunta es cierta si y solo si \( f(n)=1 \) pero esto implica que no es para toda \( f(n) \), por tanto la proposión es falsa

Pero no entiendo exactamente como razonas. Para mostrar que no es cierta para toda \( f(x)  \)te bastaría dar un ejemplo donde falle.

Por definición \( f(n)\in O(f(n)^2) \) significaría que existe un \( n_0 \) y \( c>0 \) tal que:

para \( n\geq n_0 \) se cumple \( 0\leq |f(n)|\leq c|f(n)^2| \)

Equivalentemente, para \( n\geq n_0 \) se cumple \( 0\leq \dfrac{1}{c}\leq |f(n)| \)

Por tanto el resultado es cierto para cualquier \( f(n) \) tal que  \( |f(n)|  \)esté acotada inferiormente por una cota mayor que cero, a partir de un cierto \( n \).

De ahí es inmediato dar un ejemplo donde no se cumpla.

Saludos.

[Euclides]

El problema es que tomé la desición de hacerlo sin contraejemplo, porque la primera idea que se me vino fué esa.
De la regla del producto saco eso, osea a partir de ella puedo concluir lo que quiero probar, creo que a lo que tú vas es que no lo hice por la definición....Ahora mi pregunta va....es válido lo que hice o no es concreta la demostración?

[Luis Fuentes]

Hola

Ahora mi pregunta va....es válido lo que hice o no es concreta la demostración?

No; no es correcta. Tienes dos errores:

Determine si \( f(n)\in{O(f(n)^2)} \) es verdadera:
Es falsa, veamos porqué:
de la regla del producto vemos que:
Si \( f(n)\in{O(f(n))} \) y \( 1\in{O(f(n))}\Longrightarrow{ f(n)\in{O(f(n)^2)}} \)
La primera de las primeras es evidentemente cierta, mietras que la segunta es cierta si y solo si \( f(n)=1 \) pero esto implica que no es para toda \( f(n) \), por tanto la proposión es falsa

En primer lugar la afirmación en rojo no es cierta. \( 1\in O(f(n)) \) si existe un \( n_0 \) y un \( c>0 \) tal que  \( 1\leq c|f(n)| \) para \( n\geq n_0 \). Es decir, si para \( n \) suficientemente grande \( |f(n)| \) está acotada inferiormente por una cota no nula.

En segundo lugar, en principio a la propiedad de la notación O con respecto al producto no se le puede dar la vuelta, es decir, no es cierto en general que:

\( f_1(n)f_2(n)\in O(g_1(b)g_2(n))\quad \Rightarrow{}\quad f_1(n)\in O(g_1(n)) \) y \( f_2(n)\in O(g_2(n)) \)

Entonces, si más aclaraciones, que usando esa regla no puedas deducir que \( f(n)\in O(f(n)^2) \) no significa necesariamente que esa pertenencia sea falsa.

Saludos.