# 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.