math - 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 を取ります。2n = Θ(n) であるため、f(n) = Θ(g(n)) となります。

ただし、2 ^f(n) = 2 ²ⁿ = 4 ⁿおよび 2 ^g(n) = 2 ⁿですが、4 ⁿ ≠ Θ(2 ⁿ ) です。あなたはこれを見ることができます

リム_{n → ∞} 4 ⁿ / 2 ⁿ

=リム_{n → ∞} 2 ⁿ

= ∞

お役に立てれば！