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$
2
  • $\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, 2020 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, 2020 at 14:20

1 Answer 1

Reset to default
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$
2
  • $\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, 2020 at 14:31
  • 1
    $\begingroup$ Yes. Of course, correct is $2^n=O(3^n)$. $\endgroup$
    – zkutch
    Nov 23, 2020 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.