Algoritmos

Probar si son verdaderas o no las siguientes proposiciones:
f(n) = O(g(n))  g(n) = O(f(n))
La proposición es Falsa, debido a que:
f(n) = O(g(n)) si existen dos constantes positivas c y notales que 0 ≤ f(n) ≤ c g(n) para todo n ≥ no
Esto implicaría que:
g(n) = O(f(n)) si existen dos constantes positivas c y no tales que 0 ≤ g(n) ≤ c f(n) para todo n ≥ no
Entonces si:
f(n) ≤ c g(n) ⇒g(n) ≤ c f(n) y dividiendo todo entre c tenemos que:
(f(n))/c ≤ g(n) ⇒ (g(n))/c ≤ f(n) pero si f(n) = n y g(n) = n2 y c=1 Tendríamos que:
n ≤ n2 lo cual se cumple, pero n2 ≤ nno se cumple dado que n se incrementa de forma indefinida.

f(n) + g(n) = (max (f(n) , g(n)))

Es verdadera, debido a que:
Usando la propiedad de simetría tenemos que:
 ( f(n) + g(n) ) =max ( f(n) , g(n) ) ahora se define la función h(n) = max ( f(n) , g(n) ) y entonces
h(n) = f(n) if f(n) ≥ g(n) , g(n) if f(n) < g(n)

Como f(n) y g(n) son asintóticamente no negativos,existe no tal que f(n) ≥0 y g(n)≥0 para todo n≥no.
Entonces, para n ≥ no, se tiene que f(n) + g(n) ≥ f(n) ≥ 0 y f(n) + g(n) ≥ g(n) ≥ 0. Ya que para cualquier n, h(n) es f(n) o g(n), se tiene que f(n)+ g(n) ≥ h(n) ≥ 0, lo cual demuestra que
h(n) = max( f(n), g(n)) ≤ c2( f (n) + g(n)) para toda n ≥ no por lo tanto c2 = 1.

Igualmente, puesto que para toda n, h(n) es el mayor de f(n) y g(n), setiene que para todo n ≥no,
0 ≤ f (n) ≤ h(n) y 0 ≤ g(n) ≤ h(n). Añadimos esto a las 2 desigualdades 0 ≤ f (n) + g(n) ≤ 2h(n), lo que equivale a 0 ≤ ( f (n) + g(n))/2 ≤ h(n), lo cual demuestra queh(n) = max( f (n), g(n)) ≥ c1( f (n)+g(n) para toda n ≥no, Por lo tanto c1=1/2.

Por ultimo, se tiene que: f(n) + g(n) ≥ h(n) ≥ (f(n)+g(n))/2. Entonces, por definición, tenemos que como f(n) =max(f(n),g(n)) = (f(n) + g(n)) (tomando c1 = 1/2 y c2 = 1 en la definición de ). Por simetría tenemos que: f(n) + g(n) = (max(f(n),g(n))).

f(n) = O((f(n))2)

Es falsa, pues:

Si f(n) =...