Section 3.2 #42

Posted on March 4, 2016 by Andy

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

  2. Kate Poirier says:
    March 7, 2016 at 3:06 pm

    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)}).

    Reply

Leave a Reply

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