CODEWITHSUNDEEP
algorithmbig-o
user1253637
user1253637

Reputation: 237

If f(n) ∈ ω(g(n)), then 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) )

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

It should be :

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

Could some one please verify this?

Upvotes: 1

Views: 1729

Answers (1)

IVlad
IVlad

Reputation: 43477

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

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

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

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

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

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.

Upvotes: 1

Related Questions