+1 vote
Given f(n) = o(g(n)), prove that 2^f(n) = o(2^g(n))
in Asymptotic Analysis by AlgoMeister (1.6k points)

5 Answers

0 votes
lim(F/G)=C <- lim(f/g)=C
by AlgoMeister (968 points)
0 votes
f(n) = o(g(n)) means 0<= f(n) < g(n) for all n>= n0

as f(n) is always less than g(n) and both are positive

2^f(n) < c. 2^g(n) for all n >= n0 and c is a constant

Therefore we can say that 2^f(n) = o (2^g(n)) when f(n) = o(g(n))
by AlgoMeister (688 points)
–1 vote
f(n)=o(g(n)), so we have

for any arbitrarily small c we can find a N, s.t. ALL n>N  f(n)<cg(n).

2^n grows strictly with n. so we have

2^f(n)<2^(cg(n)), 2^f(n)<(2^g(n))^c.

we find another arbitrarily small number w, then we must have

2^f(n)<w*((2^g(n))^c/w).

We just need to prove that with an large number M found s.t. ALL n>M  (2^g(n))^c/w<2^g(n).

substitute x=2^g(n). when n is large enough, it is the same with x.

we just need to prove that for arbitrarily small w and c we can find a X  s.t. ALL x>X   x^c<x*w.

X^(c-1)<w, s.t. X^(1-c)>1/w, X>(1/w)^(1/(1-c)).

We can find such a X, so we can find such a M. s.t. ALL n>M

 2^f(n)<w*((2^g(n))^c/w)<w*2^g(n), for arbitrarily small w and c.

this is the definition of small o.

So we have 2^f(n)=o(2^g(n)).

Q.E.D.
by AlgoStar (380 points)
–1 vote

f(n) = o(g(n)) ==> f(n) < c g(n) - m for any constant m, any c>0 and n>n0 

when c =1, f(n) < g(n) - m for all n>n0

Need to prove: 2^f(n) < a 2^g(n) for any a>0 and all n>n0'

if a >= 1, it's obvious 2^f(n) < a 2^g(n) for all n>n0

if 0 < a < 1, let b = 1/a; b > 1,

for n>n0 (this means n0' >= n0) , we can reason backward like this:

2^f(n) < a 2^g(n) 2^f(n)  <==  2^f(n) < (1/b) 2^g(n)  <== 2^f(n) < 2^log(1/b) 2^g(n)  <==

2^f(n) < 2^(g(n) - logb)  <==  f(n) < g(n) - logb which is proven at the beginning, where m could be logb.

PS: "f(n) = o(g(n)) ==> f(n) < c g(n) - m" this is straightforward and can be easily proven by L' Hopital's Rule.

by AlgoMeister (752 points)
–2 votes

now f(n) = o(g(n))

lim n->infinity (f(n)/g(n)) = 0

lim n->infinity (2^f(n)/2^g(n)) =  lim n->infinity (2^(f(n) - g(n)))

                                              = lim n->infinity (2^(f(n) - g(n)))

                                              = lim n->infinity (1/(2^(g(n)*(1-f(n)/g(n)))))

cuz lim n->infinity (f(n)/g(n)) = 0

lim n->infinity (2^f(n)/2^g(n)) = lim n->infinity (1/2^g(n))

if g(n) -> infinity for n -> infinity

lim n->infinity (2^f(n)/2^g(n)) = 0

as a result 2^f(n) = o(2^g(n))

else

it is not necessary that 2^f(n) = o(2^g(n))

by (124 points)
Hi Dongxing, why other condition is unnecessary? For example, f(n)->0, g(n)->0, lim n->infinity(f(n)/g(n))=0.
Hi Taoran
I am sorry that I don't get what u express
However, let's assume that f(n) = 1/n^2 g(n) = 1/n  then f(n) = o(g(n))right?
Maybe you will find the limit of 2^(f(n)-g(n)) is 1.
But the limit should be zero according to the small o definition, right?

Related questions

The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...