In einem früheren Problem habe ich (hoffentlich richtig) gezeigt, dass f (n) = O (g (n)) lg (f (n)) = O (lg (g (n))) mit ausreichenden Bedingungen (z. B. lg) impliziert (g (n))> = 1, f (n)> = 1 und ausreichend großes n).

Nun muss ich beweisen ODER widerlegen, dass f (n) = O (g (n)) 2 ^ (f (n)) = O (2 ^ g (n)) impliziert. Intuitiv ist das sinnvoll, also dachte ich, ich könnte es mit Hilfe des vorherigen Theorems beweisen. Mir ist aufgefallen, dass f (n) als lg (2 ^ f (n)) umgeschrieben werden kann und dass g (n) nur lg (2 ^ g (n)) ist, was mich aufgeregt hat ... das nimmt das Protokoll Basis 2 von beiden Seiten von dem, was ich beweisen möchte, und es vereinfacht die Dinge sehr!

Aber ich bin mir ziemlich sicher, dass das nicht funktionieren wird. Nur weil lg (2 ^ f (n)) = O (lg (2 ^ g (n))) ist, heißt das nicht unbedingt, dass 2 ^ f (n) = O (2 ^ g (n)) ... das ist rückwärts aus dem vorhergehenden Satz (der besagte "impliziert", nicht "wenn und nur wenn").

Muss ich diesen Beweis auf eine andere Weise versuchen, oder kann ich tatsächlich von dem abweichen, was ich habe (zumindest als Starter)?

** Apropos andere Möglichkeiten, vielleicht könnte ich nur darüber streiten, wie das Erhöhen von 2 auf ein g (n), das "über" einem f (n) liegt, es immer noch höher hält. Es fühlt sich fast wie ein gesunder Menschenverstand an, aber vielleicht fehlt mir etwas Wichtiges.

** Oh, hoppla! Ich habe vergessen hinzuzufügen, dass f (n) und g (n) asymptotisch positiv sind. Nach unserer Lehrbuchdefinition bedeutet dies, dass sie "für alle ausreichend großen n positiv" sind.