В предыдущей задаче я показал (надеюсь, правильно), что f (n) = O (g (n)) влечет lg (f (n)) = O (lg (g (n))) с достаточными условиями (например, lg (г (н))>= 1, f (n)>= 1 и достаточно большое n).

Теперь мне нужно доказать ИЛИ опровергнуть, что f (n) = O (g (n)) влечет 2 ^ (f (n)) = O (2 ^ g (n))). Интуитивно это имеет смысл, поэтому я решил, что смогу доказать это с помощью предыдущей теоремы. Я заметил, что f (n) можно переписать как lg (2 ^ f (n)), а g (n) - просто lg (2 ^ g (n)), что меня взволновало ... это заносит журнал База 2 обеих сторон того, что я хочу доказать, и это многое упрощает!

Но я'Я уверен, что это победилот работа. То, что lg (2 ^ f (n)) = O (lg (2 ^ g (n))) не обязательно означает, что 2 ^ f (n) = O (2 ^ g (n)) ..., что 'в обратном направлении от предыдущей теоремы (которая сказала "означает»неесли и только если").

Мне нужно попробовать это доказательство по-другому, или я действительно могу отказаться от того, что у меня есть (по крайней мере, для начала)?

** Говоря о других способах, может быть, я мог бы просто поспорить о том, как повысить 2 до некоторого значения g (n)выше" а f (n) все равно будет держать его выше? Это похоже на аргумент здравого смысла, но, может быть, яя упускаю что-то важное ..

** Ой, упс! Я забыл добавить, что f (n) и g (n) асимптотически положительны. По определению нашего учебника это означает, что они "положительно для всех достаточно больших п. "