1

How can I prove that this is true/false:

$$\log(3^n) \in O(\log(2^n))\ ?$$

I know $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such that: $$f(n) \le C \cdot g(n)$$ whenever $n > k$.

I think that the plot shows that it is not in $O(\log(2^n))$. Can I prove it with $$0 \leq \lim\limits_{n \to \infty} \dfrac{g(n)}{f(n)} < \infty\ ?$$ Thanks in advance!

EDIT: Thanks, I found the answer, the hint that it is a linear function help me! It is true for big-O and also true for big-$\Omega$.

Rócherz
  • 3,976
Cal
  • 21

1 Answers1

10

$$ \log(3^n) = n \log(3) = n \log(3) \frac{\log(2)}{\log(2)} = n \log(2) \frac{\log(3)}{\log(2)} = C \log(2^n) $$

lhf
  • 216,483
  • Thanks! I don't really understand this part: $= n \log(3) \frac{\log(2)}{\log(2)} = n \log(2) \frac{\log(3)}{\log(2)}$ looks like a change of the base. – Cal Mar 13 '16 at 10:25
  • 1
    @Cal, it's not a change of the base, just commutativity of multiplication: $\log(3) \log(2)= \log(2)\log(3)$. – lhf Mar 14 '16 at 00:44