Necesito ayuda para probar que si f(n) = O(g(n)) implica 2^(f(n)) = O(2^g(n)))

Revisamos exhaustivamente cada una de las reseñas en nuestra página web con el objetivo de enseñarte en todo momento la información certera y actual.

Solución:

Bueno, ni siquiera es true para empezar.

Digamos que el algoritmo A toma 2n pasos y el algoritmo B toma n pasos. Entonces su razón es una constante.

Pero la razón de 2²ⁿ y 2^norte no es una constante, entonces lo que dijiste no se sostiene.

Si f(n) = O(g(n)),
2^(f(n)) no es igual a O(2^g(n)))

Sea, f(n) = 2log n y g(n) = log n
(Supongamos que log está en base 2)

Sabemos, 2log n <= c(log n) por lo tanto f(n) = O(g(n))

2^(f(n)) = 2^log n^2 = n^2
2^(g(n)) = 2^log n = n

Lo sabemos
n^2 no es O(n)

Por lo tanto, 2^(f(n)) no es igual a O(2^g(n)))

Reseñas y valoraciones de la guía

---

---

Utiliza Nuestro Buscador