如果f(n)∈ω(g(n)),然后2 ^ f(n)∈ω(2 ^ g(n))

I have to find whether the following is true or false:

我必须找出以下是真的还是假的:

If f(n) ∈ ω(g(n)), then 2 ^ f(n) ∈ ω(2 ^ g(n) )

如果f(n)∈ω(g(n)),然后2 ^ f(n)∈ω(2 ^ g(n))

I did the calculations f(n) = 1/n and g(n) = 1/n^2 and got the ans as false.

我做了计算f(n)= 1 / n和g(n)= 1 / n ^ 2,俺们是假的。

It should be :

应该是:

If f(n) ∈ ω(g(n)), then 2 ^ f(n) ∈ Θ(2 ^ g(n) )

如果f(n)∈ω(g(n)),然后2 ^ f(n)∈Θ(2 ^ g(n))

Could some one please verify this?

谁能证实一下吗?

1 个解决方案

#1

Statement: f(n) ≥ g(n) ⋅ k for all k ⇒ 2^f(n) ≥ 2^g(n)⋅k for all k.

声明:f(n)≥g(n)⋅k为所有k⇒2 ^ f(n)≥2 ^ g(n)⋅k k。

Your counterexample is correct: 1/n ≥ k/n² is true for all k. We can show this by taking the limit:

你的反例是正确的:1 / n≥k / n²适用于所有k。我们可以显示这个的限制:

limn → ∞ (1 / n) / (k / n²) = 1/k ⋅limn → ∞ n² / n = ∞

描写→∞(1 / n)/(k / n²)= 1 / k⋅描写→∞n²/ n =∞

However: 21/n ≥ 21/n² ⋅ k is false. We can also show this by taking the limit:

然而:21 / n≥21 / n²⋅k是错误的。我们也可以用极限来表示:

limn → ∞ 21/n / (21/n² ⋅ k) = = 1/k lim of 21/n - 1/n² = = 1/k lim of 2(n - 1) / n² = 1/k ⋅ 2⁰ = = 1/k

描写→∞21 / n /(21 / n²⋅k)= = 1 / k lim 21 / n - 1 / n²= = 1 / k lim 2(n - 1)/ n²= 1 / k⋅2⁰= = 1 / k

The statement would only have been true if the limit was infinity.

只有当极限为无穷大时，这个表述才成立。

A single counterexample is enough to prove that a statement is false, so you're done.

一个反例就足以证明一个陈述是错误的，所以你就做完了。