Test 1 #6 (Version A)

Let f(x) and g(x) be functions from the set of positive real numbers to the set of real numbers. Assume that f(x) is O(g(x)). Does it follow that 2^{f(x)} is O(2^{g(x)}? Explain your answer.

The statement is not true. To show this, we just need to find one counterexample. That is, we need to find a function f(x) and another function g(x) so that f(x) is O(g(x)) but 2^{f(x)} is not O(2^{g(x)}.

Eric posted a nice counterexample here as a correction for a Test #1 Review question.

This entry was posted in Test #1 Solutions. Bookmark the permalink.

1 Response to Test 1 #6 (Version A)

  1. Kate Poirier says:

    This was one of the harder questions on the test. Since the function 2^x is increasing, it is true that if f(x) \leq g(x), then 2^{f(x)} \leq 2^{g(x)}. However, it is *not* true that if f(x) is O(g(x)), then 2^{f(x)} is O(2^{g(x)}). This can be counter-intuitive if you haven’t completely understood big-O notation.

    There are many different counterexamples that you can choose to see this. I saw a few others as I was grading your work, but the proofs that they were counterexamples were not always clear.

Leave a Reply

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