Why is $3^n$ not in $\Theta(2^n)$

Question

How is it that $3^n$ not in $\Theta(2^n)$, while $log_3 n$ is in $\Theta(log_2 n)$ ?

Answer 1

You can take any logarithm and convert to a different base simply by multiplying by a constant, so $\log_a(n)$ is $\Theta(\log_b(n))$ for any $a,b>1$.

It suffices to show that $3^n$ is not $O(2^n)$, i.e., you need to find $n$ such that $3^n > C2^n$, or $n \ln 3 > n \ln 2 + \ln C$, or $n > \ln C / (\ln 3 - \ln 2)$. It's easy to see from the last inequality that there's always such an $n$ for any $C$.

So while you can say that an algorithm is "$\log n$," and that means pretty much the same thing for any base, you can't say the same thing about "exponential in $n$." You need to be specific about what base you're referring to. For that reason, many theoretical computer scientists take the notation "$2^{O(n)}$" to be "exponential," because this covers any base.

EDIT: I felt like this deserved a response to the "why" part, and I think the answer to that would be that if $f(n)$ is $\Theta(g(n))$, you can't expect that $f^{-1}(n)$ is $\Theta(g^{-1}(n))$ in general. The result is especially apparent when you try to do this when $f$ and $g$ are logarithmic. You have to deal with $C$ (actually $C_O$ and $C_\Omega$, since a $\Theta$ bound is made up of two other bounds), and once you take exponents the problem pops right out -- that $C$ goes into the exponent and is no longer a simple scalar factor.

Answer 2

Short answer: The logarithms differ by a constant factor, the exponentials by the factor of $(3/2)^n$ which tends to $\infty$.

A slightly more elaborate explanation is that the $\Theta$ notation can swallow a constant factor, but not a more ''rapidly increasing'' difference. When you apply logarithms, things generally increase ''slowly'' so the difference is not likely to be so significant. For instance, $3^n \neq \Theta(2^n)$, but $\log 3^n = n \log 3 = \Theta(\log 2^n) = \Theta(n)$.