# Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?

I thought they did, but recently I tried to express $$3^n$$ as $$k \times 2^n + o(2^n)$$ for some constant $$k$$ but wasn't able to. All I found was $$3^n = (\frac{3}{2})^n 2^n$$. What am I misunderstanding here?

I suppose my question applies to $$log_c(n) = O(log_2(n))$$ as well.

• $c^n\neq O(2^n)$. Actually, $c^n=O(a^n)$ for any $a\geq c$. But $log_c(n)=(log_2(n))/(log_2(c))=O(log_2(n))$. I prefer you to look at the definition of O again. Nov 23, 2020 at 13:45
• @user5876164 Why would I need to look at the definition of O? It's perfectly clear for me. Nov 23, 2020 at 14:20

Additionally to already answered in user5876164's comment let me say, that you cannot express $$3^n=k \times 2^n+o(2^n)$$, because if we assume it for some $$k$$, then we obtain: $$\left(\frac{3}{2}\right)^n=k+o(1)$$, which is impossible, as $$\left(\frac{3}{2}\right)^n \to \infty$$.
• Ok, so my reasoning was correct, it was rather me presuming that $3^n = O(2^n)$ for a long time was incorrect. Nov 23, 2020 at 14:31
• Yes. Of course, correct is $2^n=O(3^n)$. Nov 23, 2020 at 14:58