前の問題で、私は十分条件（例えば、、そして十分に大きいn）をf(n) = O(g(n))意味することを（うまくいけば正しく）示しました。lg(f(n)) = O(lg(g(n)))lg(g(n)) >= 1, f(n) >= 1
今、私はそれをf(n) = O(g(n))意味することを証明または反証する必要があり2^(f(n)) = O(2^g(n)))ます。直感的には、これは理にかなっているので、前の定理の助けを借りてそれを証明できると思いました。それは次のように書き直すことf(n)ができることに気づきました。それは私を興奮させました...これは私が証明したいことの両側の対数基数2を取り、それは物事を非常に単純化します！lg(2^f(n))g(n)lg(2^g(n))
しかし、これはうまくいかないと確信しています。必ずしもlg(2^f(n)) = O(lg(2^g(n)))それを意味するわけではない2^f(n) = O(2^g(n))からです...それは前の定理（「もしも」ではなく「含意」と言った）から逆になっています。
この証明を別の方法で試す必要がありますか、それとも実際に（少なくともスターターとして）持っているものから離れることができますか？
g(n)**他の方法について言えば、2を「上」に上げると、f(n)それでもそれを高く保つことができるかどうかについて議論することができますか？常識的な議論のように感じますが、何か重要なことが欠けているのかもしれません。
**おっと！私はそれを追加するのを忘れてf(n)おりg(n)、漸近的にポジティブです。私たちの教科書の定義によれば、これはそれらが「十分に大きいすべてのnに対して正である」ことを意味します。