0
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – user5876164 Nov 23 '20 at 13:45
  • $\begingroup$ @user5876164 Why would I need to look at the definition of O? It's perfectly clear for me. $\endgroup$ – J. Schmidt Nov 23 '20 at 14:20
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
  • $\begingroup$ Ok, so my reasoning was correct, it was rather me presuming that $3^n = O(2^n)$ for a long time was incorrect. $\endgroup$ – J. Schmidt Nov 23 '20 at 14:31
  • 1
    $\begingroup$ Yes. Of course, correct is $2^n=O(3^n)$. $\endgroup$ – zkutch Nov 23 '20 at 14:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.