Potrzebuję pomocy, aby udowodnić, że jeśli f (n) = O (g (n)) oznacza 2 ^ (f (n)) = O (2 ^ g (n)))

W poprzednim problemie pokazałem (miejmy nadzieję, że poprawnie), że f (n) = O (g (n)) oznacza lg (f (n)) = O (lg (g (n))) z wystarczającymi warunkami (np. Lg (g (n))> = 1, f (n)> = 1 i wystarczająco duży n).

Teraz muszę udowodnić LUB obalić, że f (n) = O (g (n)) oznacza 2 ^ (f (n)) = O (2 ^ g (n))). Intuicyjnie ma to sens, więc doszedłem do wniosku, że mogę to udowodnić z pomocą poprzedniego twierdzenia. Zauważyłem, że f (n) można przepisać jako lg (2 ^ f (n)), a g (n) to tylko lg (2 ^ g (n)), co mnie podnieciło ... to zabiera dziennik podstawa 2 obu stron tego, co chcę udowodnić, a to bardzo upraszcza rzeczy!

Ale jestem pewien, że to nie zadziała. Tylko dlatego, że lg (2 ^ f (n)) = O (lg (2 ^ g (n))) niekoniecznie oznacza, że ​​2 ^ f (n) = O (2 ^ g (n)) ... to jest wstecz z poprzedniego twierdzenia (które mówi „sugeruje”, a nie „jeśli i tylko wtedy”).

Czy muszę wypróbować ten dowód w inny sposób, czy mogę zrezygnować z tego, co mam (przynajmniej jako starter)?

** Mówiąc o innych sposobach, może mógłbym po prostu spierać się o to, jak podniesienie 2 do jakiegoś g (n), które jest „powyżej” f (n), nadal będzie utrzymywać je wyżej? To prawie jak zwykły rozsądek, ale może brakuje mi czegoś ważnego ...

** Oh, oops! Zapomniałem dodać, że f (n) ig (n) są asymptotycznie dodatnie. W naszej definicji podręcznika oznacza to, że są „pozytywne dla wszystkich wystarczająco dużych n”.

questionAnswers(2)

yourAnswerToTheQuestion