1

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

Prove or disapprove the statement: $$f(n)=O(g(n)) \Rightarrow 2^{f(n)}=O(2^{g(n)})$$

That's what I have tried:

$$f(n)=O(g(n)), \text{ so } \exists c>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: f(n) \leq c g(n) \Rightarrow 2^{f(n)}\leq2^{cg(n)} (1)$$

$$2^{f(n)}=O(2^{g(n)}) \text{ means that }: \exists n_0' \geq 1 \text{ and } c'>0 \text{ such that } 2^{f(n)} \leq c'2^{g(n)} (2)$$

For $f(n)=cn, g(n)=n: (1) \Rightarrow 2^{cn} \leq 2^{cn} \checkmark$

$(2) \Rightarrow 2^{cn} \leq c' 2^{n} \Rightarrow 2^{(c-1)n} \leq c' \Rightarrow (c-1)n \leq lg c' \leq n \Rightarrow n \leq \frac{\lg c'}{c-1} \text{ that cannot be true,because it must be } n \geq n_0$

Could you tell me if it is right?

Antonio Vargas
  • 24,993
evinda
  • 7,823

1 Answers1

4

I think your argument is mostly correct - assuming you're trying to disprove the statement. But remember: disproving a universal statement means just exhibiting a single counterexample. I like your $f$ and $g$, but I wouldn't use the same $c$ in the definition of $f$ and in the $O$-property. So just show that $f(n)=2n$, $g(n)=n$ is a counterexample. Showing $f(n)=O(g(n))$ is easy of course. Then you have to show that $2^{2n}$ is not $O(2^n)$. In other words, you need to prove the negation of the $O$ definition, which is:

For every $c>0$ and for every $n_0\ge1$, there exists $n\ge n_0$ such that $2^{2n} > c2^n$.

Keeping track of exactly what statement you have to prove is half the battle (that's what will convert your ideas and preliminary computations into a proof).

Greg Martin
  • 78,820
  • I understand..thank you very much!!! – evinda Jul 13 '14 at 22:45
  • Greg Martin Could I also disapprove the statement in an other way,rather that finding a counterexample? – evinda Jul 30 '14 at 17:18
  • 1
    The statement is a universal ("for all") statement. Disproving a statement means proving its negation. The negation of a universal statement is an existential ("there exists") statement. By far the most common way to prove an existential statement (particularly in course exercises) is by giving an explicit example (which is thus a counterexample to the original statement). So while it is possible to disprove your statement without giving a counterexample, a counterexample should be the first thing you think of. – Greg Martin Jul 30 '14 at 19:36
  • 1
    I understand..thank you very much!!! :) – evinda Jul 30 '14 at 23:36
  • @GregMartin For the counter example how did you think that you should chose $f(n)=2n$ and $g(n)=n$ – clarkson Nov 19 '14 at 09:48
  • The basic idea is that exponentiating a function hugely magnifies the differences between the functions. We need $f(n) > g(n)$ to have any hope of a counterexample; and since we also need $f(n) = O(g(n))$, the easiest possible counterexample is $f(n) = Cg(n)$ for some constant $C>1$. At that point, you'll find that just about any choice of $g(n)$ actually works; so take the simplest $g(n)$ you can think of, $g(n)=n$, and the simplest choice of constant, $C=2$. – Greg Martin Nov 19 '14 at 22:26