En un problema anterior, mostré (con suerte correctamente) que f (n) = O (g (n)) implica lg (f (n)) = O (lg (g (n))) con condiciones suficientes (por ejemplo, lg (g (n))> = 1, f (n)> = 1, y n suficientemente grande).

Ahora, necesito probar O refutar que f (n) = O (g (n)) implica 2 ^ (f (n)) = O (2 ^ g (n))). Intuitivamente, esto tiene sentido, así que pensé que podría probarlo con la ayuda del teorema anterior. Noté que f (n) se puede reescribir como lg (2 ^ f (n)) y que g (n) es solo lg (2 ^ g (n)), lo que me emocionó ... esto es tomar el registro Base 2 de ambos lados de lo que quiero probar, ¡y simplifica mucho las cosas!

Pero estoy bastante seguro de que esto no funcionará. Solo porque lg (2 ^ f (n)) = O (lg (2 ^ g (n))) no significa necesariamente que 2 ^ f (n) = O (2 ^ g (n)) ... eso es al revés del teorema anterior (que decía "implica", no "si y solo si").

¿Debo probar esta prueba de otra manera, o puedo realmente dejar lo que tengo (al menos como titular)?

** Hablando de otras maneras, tal vez podría discutir sobre cómo elevar 2 a algo g (n) que está "arriba" y f (n) todavía lo mantendrá alto. Casi se siente como un argumento de sentido común, pero tal vez me esté perdiendo algo importante ...

** Oh, oops! Olvidé agregar que f (n) yg (n) son asintóticamente positivos. Según nuestra definición de libro de texto, esto significa que son "positivos para todos los n suficientemente grandes".