CODEWITHSUNDEEP
algorithmasymptotic-complexityproof
ehhpitome
ehhpitome

Reputation: 49

Proving that f(n) = o(g(n)) implies 2^f(n) = o(2^g(n))

I can't find a counterexample to this, but I do not know a formal way of proving it. Can anyone lead me in the right direction?

This is "little-o" notation by the way. So a strict upper bound

f(n) = o(g(n)) implies $ 2^{f(n)} = o(2^{g(n}) $

Upvotes: 1

Views: 4218

Answers (2)

fjardon
fjardon

Reputation: 7996

Here is a counter-example:

f(n) = 1/n
g(n) = 1

We have: f(n)/g(n) -> 0 when n -> oo, so f and g verifies: f(n) = o(g(n)).

But:

2^f(n) = 2^(1/n) -> 1 when n -> oo
2^g(n) = 2^1     -> 2 when n -> oo

And this leads to:

[2^f(n)]/[2^g(n)] -> 1/2 when n -> oo

This proves that 2^f(n) != o(2^g(n)).

Upvotes: 1

Vivek Pratap Chaurasia
Vivek Pratap Chaurasia

Reputation: 7

i would like to make correction here, i came across my old notes and realize that what i have stated is completely wrong.

explanation is as following:

lets say f(n)=2n and g(n)=n;

so according to the given problem take power both sides and it will be

  • 2^2n=2^n;
  • 2^n*2^n=2^n;
  • and it is not satisfying the asymptotic condition because left hand side is no constantly comparable to the right hand side.

Upvotes: 0

Related Questions