Clever Geek Handbook

If f (n) = o (g (n)) then 2 ^ (f (n)) = o (2 ^ (g (n)))?

Note that I am asking a little o here (see a similar question here ) - for the big O, this is clearly wrong - for the little o, it feels good, but maybe it seems to prove it ...

EDIT: glad I brought up a discussion :) Suppose f, g> 0 for simplicity

+3


source to share


3 answers


At least if g (n) converges to positive infinity for n to positive infinity (if g (n) is not, then it is easy to find counterexamples).

Proof sketch:

Prerequsites: g (n) converges to positive infinity for n to positive infinity.

f (n) in o (g (n)) means:

for every eps > 0 exists a n0 so that for all n > n0 abs(f(n)) < abs(g(n)*eps).

Formulate it like this:

2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) (for n > n0).

For eps <1:

(2^eps)^n is in o(2^n) (as 2^eps < 2)

it follows that for any eps2> 0 there exists n1, so for all n> n1

(2^eps)^n < eps2*(2^n).

Selection eps2 = eps vields:

(2^eps)^n < eps*(2^n) for all n > n1 (n1 is dependent on eps)

Since g (n) → pos. inf. for n → pos. inf. there is n2 so that

g(n) > n1 for all n > n2

After that there is

(2^eps)^g(n) < eps*2^g(n) for all n > n2.


So, for every 0 <eps <1, there is n3> = max (n0, n2), so

2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) < eps*2^g(n) for all n > n3.

For each eps3> 1 also:

2^abs(f(n)) < eps*2^g(n) < eps3*2^g(n)

So, for every ep> 0 there is n3, so 

2^abs(f(n)) < eps*2^g(n) for all n > n3

Becase 2 ^ f (n) 2 ^ abs (f (n)) for all n and 2 ^ x> 0 for all real x, then 

abs(2^f(n)) < abs(eps*2^g(n)) for all n > n3

qed

If something is unclear or incorrect, please comment.

EDIT: Some thoughts on other g (n):

The subsequence g (n) is bounded, i.e. there is some x, so there is no n0 with abs (g (n))> = x for all n> n0:

o (g (n)) consists only of functions that are constant 0 after some n or converge to 0. Then 2 ^ g (n) also has a bounded subsequence, but 2 ^ f (n) is constant 1 after some point.

There is no n0, so g (n)> 0 for all n> n0:

2 ^ g (n) 1 if g (n) 0, so g (n) has a bounded subsequence meaning o (2 ^ g (n)) consists only of functions that are constant 0 after some n or converge to 0 ...

+2


source


Here's the answer. The result depends on the convergence properties of g (n).

Consider the associated limit first:

lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
lim(x->inf) ( log_2(2^(f(n))) - log_2(2^(g(n))) )
=
lim(x->inf) ( f(n) - g(n) ) = lim(x->inf) ( g(n) * f(n) / g(n) - g(n) )
=
lim(x->inf) ( -g(n) ) = - lim(x->inf) g(n)

... Now, to get this in the form of the original question in your post, IF it is mathematically correct to switch the limit and log (which I think it is), then we would have:

lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
log_2 lim(x->inf) ((2^(f(n))) / (2^(g(n)))).

Now let's move on to answering the question. If the value it is true that

2^(f(n)) = o(2^(g(n))),

then in the limit the right-hand side becomes



log_2 (0) = - inf

... so in this scenario it should be true that

lim(x->inf) g(n) = inf

This result seems to make sense. Let's consider f(x) = exp(-x) and g(x) = 1 - exp(-x)

. It is clear that in this example f(x) = o(g(x))

. However 2^(f(x)) is not o(2^(g(x)))

, because

lim(x->inf) (2^exp(-x)) / (2^(1-exp(-x))) = 1/2.

But under the condition f(x) = exp(x), g(x) = exp(2x)

, where also f(x) = o(g(x))

and where lim(x->inf) g(x) = inf

, satisfying the above condition, we have

lim(x->inf) (2^exp(x)) / (2^exp(2x))
=
lim(x->inf) 1 / 2^(exp(x)*(exp(x) - 1)) = 0

so 2^(f(x)) = o(2^(g(x)))

.

+1


source


Simple proof with example,

If f (n) = O (g (n)) then 2 ^ (f (n)) is not equal to O (2 ^ g (n)))

Let f (n) = 2log n and g (n) = log n
(Suppose log is to base 2)

We know 2log n <= c (log n) so f (n) = O (g (n))

2 ^ (f (n)) = 2 ^ log n ^ 2 = n ^ 2
2 ^ (g (n)) = 2 ^ log n = n

We know n ^ 2 is not O (n)

Hence 2 ^ (f (n)) is not equal to O (2 ^ g (n)))

-1


source






More articles:


All Articles