3

Suppose that both f(n) and g(n) are non-negative functions. If $f(n)=O(g(n))$, is $2^{f(n)}=O(2^{(g(n)})$ true too? If not, give counter examples.

I am unsure of how to proceed. What I have in mind at the moment is that since f(n) and g(n) are non-negative functions, making them functions exponents to 2 (as the base) would not change their characteristics. I would appreciate help in understanding this problem and proving it.

bow_one
  • 83

1 Answers1

5

Basic idea: if $f(n)=O(g(n))$, then $$f(n)\le Cg(n)$$ and so $$2^{f(n)}\le 2^{Cg(n)}=(2^C)^{g(n)}\ .$$ If $C>1$ then this will not be a constant times $2^{g(n)}$. So a counterexample will be something like $f(n)=2n$, $g(n)=n$. I'll leave you to check the details and write this out carefully.

David
  • 82,662
  • How does $ f(n)=2n, g(n)=n$ work as a counter example? we have $2n=O(n)$ , so $2^{2n}\le c 2^{n}$ and take $c=2$ so $2^{2n} = O (2^{n})$. Can't we state that since $2^x$ is a contentious positive function then it keeps sign of inequalities? – shinzou Oct 26 '15 at 14:27
  • 1
    @kuhaku You sincerely believe that $2^{2n}\le c2^n$ for every $n$, for some finite $c$? Surely you realized that $2^{2n}=4^n$... – Did Oct 26 '15 at 14:44
  • @did well if $c=2$ then $4^n=2^{2n}\le 2\cdot2^n=4^n$ – shinzou Oct 26 '15 at 14:46
  • 1
    @kuhaku Try computing $2\cdot2^n$ and $4^n$ for $n=3$. – Did Oct 26 '15 at 14:46
  • 1
    @did yeah... damn... – shinzou Oct 26 '15 at 14:48