Big-O: If $f(n)=O(g(n))$, prove $2^{f(n)}=O(2^{(g(n)})$

asymptotics

Solution 1:

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.

Related

Prove that the sequence $x_{n+1}=\frac{a}{1+x_n}$ with $a,x_0>0$ converges
Combinatorics of the coupon collector's problem
Find all function satisfying $f(f(n))+f(n)=2n+3k$
Calculate the limit : $\lim_{x \to 0}\frac{x-\sin{x}}{x^3}$ WITHOUT using L'Hopital's rule [duplicate]
Boundaries in heat equation
Three linked question on non-negative definite matrices.
Limit of $\frac{x^y-y^x}{x^x-y^y} $ while $x\to y$
Prove $\sqrt{2} + \sqrt{5}$ is irrational [duplicate]
Formula similar to $EX=\sum\limits_{i=1}^{\infty}P\left(X\geq i\right)$ to compute $E(X^n)$?
Value of $\lim_{n \to \infty}\frac{\sqrt{1}+\sqrt{2}+\sqrt{3}+\cdots+\sqrt{n-1}}{n\sqrt{n}}$
If $f(x + y) \leq yf(x) + f(f(x))$ for all real numbers $x$ and $y$, then prove that $f(x) = 0$ for all $x ≤ 0$.
Origin of rapidly converging sequence for $e^\pi$