Prove that if $\log{f(n)} \in O(g(n))$ then $f(n)\in O(3^{g(n)})$

Question

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$ $$\forall f\in\mathcal{F}: \log{f(n)} \in O(g(n))\implies f(n)\in O(3^{g(n)}).$$

How to prove this? I thought about first showing that $$g(n) \in O(3^{g(n)})$$ Then $$\log{f(n)} \in O(f(n))$$ but that doesn't necessarily mean $$f(n)\in O(3^{g(n)}).$$ does it?

Update: This is a false statement, counter-example: f(n) = $4^x$, g(n) = x

Not true. $f/g$ bounded doesn't imply $e^f/e^g=e^{f-g}$ is bounded. — A.S., Mar 25 '16 at 20:44
Are you saying the statement is false? Could you please explain I don't quite understand, thanks — Amir Mousavi, Mar 25 '16 at 20:56
Yes, the statement is false. Try $f(x)=4^x$ and $g(x)=x$. More generally, $O(e^f)\ne e^{O(f)}$ — A.S., Mar 25 '16 at 21:14

String · Answer 1 · 2016-03-26T08:49:38.523

2

Since the exponential function is strictly increasing, it preserves inequalities when applied to both sides of an inequality so: $$ \log(f(n))\leq c\cdot g(n)\iff f(n)\leq \operatorname e^{c\cdot g(n)}=\left(\operatorname e^c\right)^{g(n)} $$ and this is only $O(3^{g(n)})$ if a constant $c\leq\log(3)$ will work.

edited Mar 26 '16 at 08:49

answered Mar 25 '16 at 20:37

String

18,395

Prove that if $\log{f(n)} \in O(g(n))$ then $f(n)\in O(3^{g(n)})$

1 Answers1