Em um problema anterior, mostrei (espero que corretamente) que f (n) = O (g (n)) implica lg (f (n)) = O (lg (g (n))) com condições suficientes (por exemplo, lg (g (n))> = 1, f (n)> = 1 e suficientemente grande n).

Agora, eu preciso provar OU refutar que f (n) = O (g (n)) implica 2 ^ (f (n)) = O (2 ^ g (n))). Intuitivamente, isso faz sentido, então imaginei que poderia provar isso com a ajuda do teorema anterior. Notei que f (n) pode ser reescrito como lg (2 ^ f (n)) e que g (n) é apenas lg (2 ^ g (n)), o que me deixou excitado ... isso é pegar o log base 2 de ambos os lados do que eu quero provar, e isso simplifica muito as coisas!

Mas tenho certeza que isso não funcionará. Só porque lg (2 ^ f (n)) = O (lg (2 ^ g (n))) não significa necessariamente que 2 ^ f (n) = O (2 ^ g (n)) ... isso é para trás do teorema anterior (que dizia "implica", não "se e somente se").

Preciso tentar essa prova de outra maneira, ou posso realmente sair do que tenho (pelo menos como uma partida)?

** Falando de outras maneiras, talvez eu pudesse apenas argumentar sobre como aumentar 2 para algum g (n) que está "acima" de um f (n) ainda irá mantê-lo maior? Quase parece um argumento do senso comum, mas talvez eu esteja perdendo algo importante.

** Oh, opa! Esqueci de acrescentar que f (n) e g (n) são assintoticamente positivos. Pela nossa definição de livro didático, isso significa que eles são "positivos para todos os suficientemente grandes n".