# 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

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

All Articles