3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I added a bit to my answer to help explain why this doesn't work both ways. $\endgroup$ Commented Jan 16, 2014 at 4:53

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ To expand on your last point, if the inverse function of $f(n)$ is $h(n)$, then the inverse function of $2f(n)$ is $h(n/2)$. While clearly $f(n)$ and $2f(n)$ have the same order, there's no particular reason why $h(n/2)$ should have the same magnitude as $h(n)$ when $h$ is a fast-growing function. Order of operations matters! $\endgroup$
    – Erick Wong
    Commented Jan 16, 2014 at 5:09
  • $\begingroup$ @ErickWong That's a really good way to put it. $\endgroup$ Commented Jan 16, 2014 at 5:10
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .