I need some help with a big O proof. I think I have a proof but I feel like some of the steps aren't logically compatible.

The Question: For all functions f,g with domain $\mathbb{N}$ that maps to $\mathbb{R}$, $log(f(n))\in \mathcal{O}(g(n)) \implies f(n) \in \mathcal{O}(3^{g(n)})$

I basically took the definiton of big O and took the last part of the inequality $log(f(n)) \le cg(n)$ then $f(n) \le e^{cg(n)} \le 3^{cg(n)}$ I know I'm close. But I have that c in the exponent. Any help?

Can I do something like $3^{cg(n)} \le c_0^{g(n)-cg(n)}$ $3^{cg(n)}$ (the $c_0$ from the definition for the part I want to prove) I know that I know the definition holds for some c since it is an if-then proof, but I can't choose c since it's a existential.

FYI (def of Big O I used): $f(n)\in\mathcal{O}(g(n))\iff \exists c \in \mathbb{R^+}: \exists B \in \mathbb{N}: \forall n \in \mathbb{N}, n \ge B \implies f(n) \le cg(n)$

  • 2
    $\begingroup$ It's not true. Let $f(n)=9^n$. Then $\log(f(n))=n\log 9=O(n)$, but it is not true that $9^n=O(3^n)$. $\endgroup$ – Thomas Andrews Mar 22 '16 at 23:30
  • $\begingroup$ True, thanks!!! $\endgroup$ – Chubbles Mar 24 '16 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.