0
$\begingroup$

(From CLRS -- 3-4,d)

Let $f(n)$ and $g(n)$ be asymptotically positive functions.

I tried to prove that $$f(n) = O(g(n)) \implies 2^{f(n)} = O\left(2^{g(n)}\right) .$$

I know that the above statement is false, so where have I gone wrong in my proof?:

Suppose $f(n) = O(g(n)).$ Then there exist positive real numbers $c, n_0$ such that for all $n \geq n_0:$ $$0 \leq f(n) \leq c g(n).$$ Raising all sides to the power of 2, we have: $$0 \leq 2^{f(n)} \leq 2^{cg(n)}$$ (we can do this because $2^n$ is an increasing function).

From this, we can say that $$0 \leq 2^{f(n)} \leq \underbrace{2^c}_{\text{arbitrary constant}}\cdot 2^{g(n)}$$ so if $d = 2^c$, we can say that $2^{f(n)} = O(2^{g(n)})$.

(I now know that $f(n) = 2n, \ \ g(n) = n$ is an easy counterexample, but I'm still struggling to find the flaw in my "proof").

$\endgroup$
  • $\begingroup$ Hint: $x^{a \cdot b} = (x^a)^b \neq x^a \cdot x^b$ $\endgroup$ – ryan Jul 5 '17 at 21:46
1
$\begingroup$

You should be able to work out the answer yourself. Here's the general procedure:

Since you know of a counterexample to the original claim, plug those $f,g$ into each step of your proof and find the first step in your proof where the proof goes wrong. In other words, find the first claim made in the proof that isn't correct for that choice of $f,g$. That will help you pinpoint the step in your proof that is flawed, i.e., that makes a conclusion that doesn't follow logically from the previous steps.

$\endgroup$
  • 1
    $\begingroup$ Ah. Got it. Silly mistake on my part. Thanks! $\endgroup$ – Spongebob Jul 5 '17 at 23:13
0
$\begingroup$

Your mistake seems to be in assuming that $a^n \cdot a^m = a^{nm}$. Rather, we have $a^n \cdot a^m = a^{n + m}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.