Test 1 #6 (Version A)

Posted on March 27, 2016 by Kate Poirier

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.

One Response to Test 1 #6 (Version A)

  1. Kate Poirier says:
    March 27, 2016 at 5:28 pm

    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.

    Reply

Leave a Reply

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