Section 3.2 #42

42. Suppose that f (x) is O(g(x)). Does it follow that 2^f (x) is O(2^g(x))?

f (x) is O(g(x)) or f(x) ≤ g(x)
Then 2^ f(x) ≤ 2^g(x)
Therefore, 2^f(x) is O(2^g(x))

This entry was posted in Homework, Test #1 Review. Bookmark the permalink.

3 Responses to Section 3.2 #42

  1. Kate Poirier says:

    This is kind of a tricky question, huh? Andy, Eric is absolutely right. It looks like in your proof you’re assuming that f(x) \leq  g(x), but this doesn’t have to be true. The statement that f(x) is O(g(x)) is strictly weaker, so you can’t use the simple inequality the way that you want to.

    Eric’s link contains a nice example of functions f(x) and g(x) such that f(x) is O(g(x)) but 2^{f(x)} is not O(2^{g(x)}).

Leave a Reply

Your email address will not be published. Required fields are marked *