0

Possible Duplicate:
If f(n) = O(g(n)) , then is exp(f(n)) = O(exp(g(n)))

I stumbled upon this question in the Cormen book.

If f(n) is O (g(n)) then 2^f(n) is also O (2^g(n)). Is this true? I was trying to prove it using limit rules but totally stuck. My instincts are saying it is false but how can we deduce that?

Thanks

Community
  • 1
  • 1
John
  • 1

2 Answers2

1

No it's not.

f(n) = 2n is O(n), but e^(2n) is O((e^2)^n), which is obviously slower than O(e^n) because of the larger base.

user541686
  • 205,094
  • 128
  • 528
  • 886
  • because of the larger exponent* – Ozzah Apr 19 '11 at 03:25
  • @Ozzah: Eh, depends on how you look at it. I assumed the larger exponent wasn't obvious, so I rearranged it to show that the base is `e^2` instead of `e`. Same difference. – user541686 Apr 19 '11 at 03:31
0

See here : If f(n) = O(g(n)) , then is exp(f(n)) = O(exp(g(n)))

Community
  • 1
  • 1
Saurabh Gokhale
  • 53,625
  • 36
  • 139
  • 164