Если f (n) = Θ (g (n)), есть 2 ^ f (n) = Θ (2 ^ g (n))?

Question

Если f (n) равно Θ (g (n)), то функция 2 ^{f (n)} всегда равна Θ (2 ^{g (n)} )? Почему или почему нет?

Answer 1

Это утверждение неверно. Возьмем f (n) = 2n и g (n) = n. Тогда f (n) = & Theta; (g (n)), потому что 2n = & Theta; (n).

Однако 2 ^{f (n)} = 2 ²ⁿ = 4 ⁿ и 2 ^{g (n)} = 2 ⁿ , но 4 ⁿ & ne; & Theta; (2 ^N ). Вы можете видеть это, потому что

lim _{n & rarr; & infin;} 4 ⁿ / 2 ⁿ

= lim _{n & rarr; & infin;} 2 ⁿ

= & infin;

Надеюсь, это поможет!