Ejercicios de práctico (2021)

Hola Lourdes. 

Tomando f(n) = 2n y g(n) = n sí se cumple que f(n) es O(g(n)).

Recordando que f(n) es O(g(n)) si existen constantes c > 0 y n₀ >= 0 tales que para todo n >= n₀ se cumple que f(n) <= cg(n).

Notar que tomando c = 5 y n₀ = 0 se cumple que para todo n >= 0 = n0, f(n) = 2n <= 5n = cg(n), que es lo que necesitamos para afirmar que f(n) es O(g(n)). ¿Se ve?

Luego, resta probar que 2^f(n)no es O(2^g(n)), es decir, que 2²ⁿno es O(2ⁿ).

Para que 2²ⁿ fuera O(2ⁿ) tendrían que existir constantes c > 0 y n₀ >= 0 tales que para todo n >= n₀ 2²ⁿ <= c2ⁿ, lo cual implicaría que existieran constantes c > 0 y n₀ >= 0 tales que para todo n >= n₀  2ⁿ <= c, lo cual implicaría que existieran constantes c > 0 y n₀ >= 0 tales que para todo n >= n₀ n <= log₂c, que es constante. Como para cualquier constante c > 0 nunca vamos a poder encontrar un n₀ tal que para todo n >= n₀se cumpla n <= log₂c se concluye que 2²ⁿno es O(2ⁿ). ¿Se ve?

Avisame si quedó un poco más claro sino lo seguimos viendo.

Saludos!