PUERTA | PUERTA 2017 MOCK II | Pregunta 17

Considere el caso: f(n) = O(g(n)).

Luego, se afirma que las siguientes dos afirmaciones se infieren del caso anterior.

Enunciado I: 2 ^f(n) = O(2 ^g(n) )
Enunciado II: 2 ^g(n) = O(2 ^f(n) )

Elija la opción correcta de las dadas.

(A) Ambos enunciados son verdaderos
(B) Ambos enunciados son falsos
(C) El enunciado I es verdadero y el enunciado II es falso
(D) El enunciado I es falso y el enunciado II es verdadero

Respuesta: (B)
Explicación: si f(n) = n y g(n) = 2n.
entonces f(n) = O(g(n))
aquí, 2^n = O(2^(2n)) = O(4^n), pero no al revés. Por lo tanto, yo es verdadero. II es falso.
————–
Ahora, si f(n) = 2n y g(n) = n
entonces también f(n) = O(g(n)) porque podemos ignorar la constante
pero, 2^(2n) != O (2^n), por lo tanto, I es falso, pero II es verdadero.

En los dos casos anteriores, f(n) = O(g(n)). Pero ambos casos son contrarios entre sí. Por lo tanto, tanto I como II están equivocados.
Cuestionario de esta pregunta