O-Notation Prove or Disprove $ 3^{O(n)} = O(8^{n})$

Question

I am really new in data algorithm and Big O-Notation and could not find a good solution for this:

$$ 3^{O(n)} = O(8^{n}) $$

First of all what does this term $ 3^{O(n)}$ mean?

I thought using the definition of O-Notation: $f(n) \leq c g(n)$. But this does not apply if $O(n)$ are on the both side or?

$2n=O(n)$ but $3^{2n}=9^n$ is ... – mfl Oct 25 '17 at 11:30 — mfl, Oct 25 '17 at 11:30

score 1 · Answer 1 · answered Oct 25 '17 at 11:31

1

We can only make sence of the claim $$ 3^{O(n)}=O(8^n)$$ as meaning

If $f(n)\in O(n)$, then $3^{f(n)}\in O(8^n)$.

But with this interretation, the claim is false: Consider $f(n)=2n$ and show that $9^n\notin O(8^n)$.

answered Oct 25 '17 at 11:31

Hagen von Eitzen

First of all thanks for the quick reply and does this mean i consider the term 3 O(n) just as f(n) and think a claim to prove this? – Newuser1234567 Oct 25 '17 at 11:45
S/he just argued that you cannot prove this. – Randall Oct 25 '17 at 11:50

1 Answers1