[Marcelo]

Hola compañeros, ¿cómo podría demostrar lo siguiente?

\(  f(n) \in O(g(n))\Rightarrow f(n)^2\in O(g(n)^2) \)

¿Elevo al cuadrado los elementos del primer conjunto para llegar a la inclusión?

[sanmath]

Hola. No, no debes elevar de esa forma al cuadrado, usa la definición.
La definición es:
\( f\in O(g) \) si existe \( n_0,c\in \mathbb{N} \) tales que
para todo \( n\geq{n_0} \) se cumple que: \( \left |{f(n)}\right |\leq{c\left |{g(n)}\right |} \).

Ahora usando esta definición deberías mostrar que si \( h(n)=f(n)^2  \) y \( k(n)=g(n)^2 \) entonces debes demostrar que \( h(n)\in O(k(n)) \).
Para ello por definición debes hallar un \( n_1\in \mathbb{N} \) y un \( k\in \mathbb{N} \) tal que:
para todo \( n\geq n_1 \) se cumpla que \( \left |{h(n)}\right |\leq{{\red k}\cdot \left |{k(n)}\right |} \).
Ahora bien, tú deseas obtener ésto:
\( \left |{f(n)^2}\right |\leq{{\red k}\cdot \left |{g(n)^2}\right |} \) pero como si elevas al cuadrado puedes quitar el valor absoluto pues es un número positivo, entonces basta mostrar que:
\( f(n)^2\leq{k\cdot g(n)^2} \)
Aquí es donde si elevas al cuadrado lo que tienes como dato, asi desaparecen los valores absolutos y basta tomar la constante k buscada como \( c^2 \) y \( n_1=n_0 \).

Saludos

Cuida la ortografía y no añadas saltos de línea innecesarios.

[Marcelo]

Hola, gracias por responderme. No logro entender por qué utilizas el módulo, si por definición las funciones son positivas, y los valores de c y n1 son positivos.

[sanmath]

Esa es la definición de orden de complejidad.

[pierrot]

Esa es la definición de orden de complejidad.

Para algunos autores, sí. Pero para otros no. De hecho, en el conocido libro Fundamentos de algoritmia de Brassard y Bratley, se define:

\( \begin{equation*}O(f(n))=\{g:\mathbb{N}\rightarrow \mathbb{R}^{\geq 0}:(\exists c>0)(\exists n_0\in \mathbb{N})(\forall n\in \mathbb{N})(n\geq n_0\rightarrow g(n)\leq c\cdot f(n)\}\end{equation} \)

La razón por la que suelen considerarse sólo funciones no negativas, es que en el contexto del análisis del algoritmos interesa determinar el orden del tiempo de ejecución \( T(n) \) de un algoritmo dado dependiendo de una entrada de tamaño \( n \); y no tiene sentido hablar de un tiempo de ejecución negativo.

De todas formas (con o sin valor absoluto), la demostración es la que ha indicado sanmath.