7

If f = O(g), is e^f = O(e^g)?

I'm having difficultly figuring out the above question. An example would be welcome. Also, if you use l'Hôpital's rule, please show how you do differentiation.

royhowie
  • 11,075
  • 14
  • 50
  • 67
Programmer
  • 6,565
  • 25
  • 78
  • 125

3 Answers3

14

This statement is wrong, for example 2n = O(n), but exp(2n) != O(exp(n)). (The latter would mean exp(2n) <= C exp(n) for sufficiently large n, i.e. exp(n) <= C which is not true.)

adamax
  • 3,835
  • 2
  • 19
  • 21
  • This is indeed a common pitfall of asymptotic analysis. Passing to the logarithm (or any function whose derivative is bounded at infinity) preserves big O though. – Alexandre C. Mar 08 '11 at 17:20
  • 1
    @Alexandre: no it doesn't. `$log(n^3) \in O(log(n^2))$`. Also note that `$3^n \notin O(2^n)$`. Using a logarithm sorts your functions into two basic complexity classes: polynomial time (logarithms of all of the polynomials are all in the same big-O class), and exponential time (logarithms of all of the exponentials are all in the same big-O class). – Ken Bloom Mar 08 '11 at 19:48
  • @Ken: oops... Okay, it works with equivalents: f ~ g => log f ~ log g hence my confusion! – Alexandre C. Mar 08 '11 at 21:13
  • There is a case where this statement is true: when f(n) = g(n) – lenkite May 19 '14 at 07:26
  • 1
    Your answer makes sense, but contradicts theorem 4 on p5: http://www.cs.cmu.edu/~jamiemmt/teaching/su-122/lectures/07-bigo.pdf . Is this theorem incorrect? – twinlakes Sep 11 '14 at 02:48
  • @twinlakes you are correct. I am having the same confusion. Can someone please acknowledge? – Core_Dumped Sep 05 '16 at 04:59
8

The claim is not correct.

A conterexample is the following: We have no doubt that 2n is element of O(n). But, we can prove that exp(2n) is not an element of O(exp(n)). This can be easily seen by computing the 

                 exp(2n)
     lim        -------- = infinity
n -> infinity     exp(n)

which implies that exp(2n) is not in O(exp(n)).

Considering your hint about L'Hospital: It is a rule for computing limits using derivatives, more precisely:

                f(x)                       f'(x)
     lim       ------  =        lim     -----------
n -> infinity   g(x)      n -> infinity    g'(x)

under certain circumstances (e.g. both f and g tend towards infinity. I do not know the exact criteria to be fulfilled, so I just suggest reading this for more information.

But, what we can say about functions and their derivatives is the following:

If f'(x) is element of O(g'(x)), then we have that f(x) is element of O(g(x)). The other direction is not the case.

phimuemue
  • 34,669
  • 9
  • 84
  • 115
0

I'll try to help you with l'Hôpital's:

$\lim_{x \to a}{f(x)\over g(x)}=\lim_{x \to a}{f'(a) \over g'(a)}

We use that in order to solve inf/inf or 0/0 indetermination. But your problem is not that I think, but maybe when you try to derive the O(g(n)) or exp(f(n)) which are composite functions.

The chain rule to derive composite functions is this: (f o g)(x) = f'(g(x)).g'(x)

if you follow that, you can derive any composite function.

Marcote
  • 2,977
  • 1
  • 25
  • 24