2

It's similar to this question but upside down.

Suppose that both $f(n)$ and $g(n)$ are nonnegative functions. If $2^{f(n)}=O(2^{(g(n)})$, is $f(n)=O(g(n))$ true too? If not, give a counterexample.

PNT
  • 4,164
ChaosPredictor
  • 303
  • 3
  • 12

2 Answers2

1

Bounded below by a positive constant is needed. What if not?

Try $f(n) = 1+1/n$ and $g(n) = 1/n$. Then $$ 2^{f(n)} = 2^{1+1/n} = 2 \cdot 2^{1/n} = 2\cdot 2^{g(n)} \quad\text{so}\quad 2^{f(n)} = O\big(2^{g(n)}\big). $$ But $$ f(n) = 1+\frac{1}{n}\quad\text{ is not } O\left(\frac1n\right)=O(g(n)) . $$

GEdgar
  • 111,679
0

$2^{f(n)} =O(2^{g(n)})$ implies there exist M a real number and $n_0 \in \mathbb{N}$ such that $|2^{f(n)}| \leq M|2^{g(n)}|$ for all $n \geq n_0$. Now take log both sides which becomes $|f(n)| \leq M^1+|g(n)|$ for all n greater than $n_0$. I think, if g(n) is bounded below by some positive number then certainly, what you are saying is true.

Shri
  • 774
  • 2
    Taking $\log_2$ of both sides of $2^{f(n)} \leq M 2^{g(n)}$ yields $f(n) \leq \log_2 M + g(n)$. How do you find an $M'$ such that $\log_2 M + g(n) \leq M' g(n)$? It's impossible if $g(n) \to 0$ and $M > 1$. – Antonio Vargas Nov 18 '17 at 01:56