6
$\begingroup$

We were doing a quick review of undergrad topics the other day in my grad Algorithms class and the professor asked a simple question: Which grows faster, $2^n$ or $3^n$? Everyone was quick to agree that $3^n$ grew faster but I opened my big mouth and said "Obviously they grow at the same rate because if you take the log of both sides they have the same asymptotic behavior." I see the mistake I made in relating the functions themselves to the ones after taking the logs but that brought up this question:

Why does taking the log of functions with different asymptotic behaviors bring them into a set of functions with the same asymptotic behavior? Does this apply to other function groups besides exponentials with different bases?

It's probably a dumb questions and I'm missing something extremely obvious. My prof said something like "logs tend to wash out or flatten functions when you use them so be careful" but I want something a bit more rigorous.

Update

Obviously taking the log of a function affects the growth rate. I realize my title is misleading abit. My question might be better stated as:

$2^n$ and $3^n$ have different asymptotic behaviors. However, after taking the log of both functions, the new functions now have the same asymptotic behavior. Why?

$\endgroup$
4
  • $\begingroup$ @CameronWilliams Yes, but that is not my question (first paragraph, last sentence is where I vaguely mention what you answered). I am interested in why taking the log of exponentials change the asymptomatic behavior as it does. $\endgroup$
    – Caleb
    Jan 26, 2014 at 4:37
  • $\begingroup$ When you say that you take the log of both functions, are you taking the log with respect to the same base, or 2 and 3 respectively? $\endgroup$
    – Tpofofn
    Jan 26, 2014 at 4:45
  • $\begingroup$ Updated the question, maybe it is more clear now! $\endgroup$
    – Caleb
    Jan 26, 2014 at 4:47
  • $\begingroup$ @Tpofofn Arbitrary log base really, let's say base 10. $\endgroup$
    – Caleb
    Jan 26, 2014 at 4:48

2 Answers 2

4
$\begingroup$

Here is a more general framework for your question. Suppose you have functions $f(x)$ and $g(x)$. You compare their growth rates by looking at $$\lim_{x\to\infty}\frac{f(x)}{g(x)}$$ In your problem, $f(x)=3^x$ and $g(x)=2^x$, and this limit is $\infty$, which is what we mean when we say "$3^x$ grows faster than $2^x$."

Then you ask: why does taking the logarithm not yield the same order? (In other words, you're asking: if $f(x)$ grows faster than $g(x)$, why doesn't $\log f(x)$ grow faster than $\log g(x)$? Or, in yet other words: why don't logs preserve the asymptotic ordering?) The answer is that you must now consider $$\lim_{x\to\infty}\frac{\log f(x)}{\log g(x)}$$ And there is no nice way to relate the first limit to this limit, in general.

But in your special case when $f(x)$ and $g(x)$ are exponentials, taking the log gives first-order polynomials, which have the same growth rate: $$\lim_{x\to\infty}\frac{\log 3^x}{\log 2^x}=\lim_{x\to\infty}\frac{x\log 3}{x\log 2}=\frac{\log 3}{\log 2}$$ (Since the limit is finite and non-zero, the new functions have the same growth rate.)

EDIT

No, pure exponentials are not the only family of functions that has this property. Consider $f(x)=x\cdot 3^x$ and $g(x)=x\cdot 2^x$. These functions have different growth rates, because $$\lim_{x\to\infty}\frac{x\cdot 3^x}{x\cdot 2^x}=\infty$$

But their logs, $\log x+x\log 3$ and $\log x+x\log 2$, have the same growth rates, because $$\lim_{x\to\infty}\frac{\log x+x\log 3}{\log x+x\log 2}=\lim_{x\to\infty}\frac{\frac{1}{x}+\log 3}{\frac{1}{x}+\log 2}=\frac{\log 3}{\log 2}$$

In fact, as this example suggests, any function that is the product of a bunch of functions all of which have growth rate at at most exponential will work: their logarithms will have the same growth rate. Take $f(x)=(\log_3 x)(x^3-4x^2+1)3^x$ and $g(x)=(\log x)(x^2)2^x$ for example. These functions have different growth rates, again, but their logarithms have the same growth rate. The logarithm turns the multiplicative structure into an additive structure dominated by a first-order polynomial.

$\endgroup$
7
  • $\begingroup$ As I said in the comments after Cameron posted on the main post, this does not answer the question. I am not trying to relate the limits but rather am interested in the analysis of why taking the log of exponential functions with different asymptotic behaviors causes them to then have the same asymptotic behavior after taking the log. $\endgroup$
    – Caleb
    Jan 26, 2014 at 5:23
  • 1
    $\begingroup$ My answer explains this exactly: you just compute the new limit, which is finite and nonzero. $\endgroup$ Jan 26, 2014 at 5:25
  • 1
    $\begingroup$ In general, the functions $a^x$ and $b^x$ with $a,b>0$ and $a\neq b$ will have different growth rates, but taking the logarithm will yield functions with the same growth rate, by the basic facts of logarithms: $\log a^x=x \log a$ and $\log b^x=x\log b$. These are first-order polynomials, which have the same growth rate. $\endgroup$ Jan 26, 2014 at 5:26
  • $\begingroup$ And here in lies my question: Why? Just stating some logs rules doesn't answer the question for me. I was hoping for something deeper and more insightful as to logarithmic effects on functions with different growth rates. Ross's answer seems a bit more insightful but have to digest it a bit before I can say for sure... $\endgroup$
    – Caleb
    Jan 26, 2014 at 5:39
  • 1
    $\begingroup$ I don't know how an answer to your question doesn't answer your question. You did not ask for 'something deep' in the question that is posted. The reason they have the same asymptotic behavior is that the logarithm of an exponential function produces a first-order polynomial, and all first-order polynomials have the same growth rates. $\endgroup$ Jan 26, 2014 at 5:41
1
$\begingroup$

Taking logs is a coarse way to compare growth rates. We say two functions grow about the same if one is within a constant factor of the other. If we take the log of each, they would then be with a constant additive number of each other. You are allowing a multiplicative factor after taking the log. This is vastly different from being within a multiplicative factor before the log.

Even though it is very coarse, it can be useful. $2^{2^n}$ is vastly less than $3^{3^n}$ and the logs will show it. As the numbers get larger, factors of $n$, or $2^n$, start not to matter at all. Both of the previous ones are so small before $2\uparrow \uparrow n$ that it is laughable. You need your comparison technique to match the magnitudes in play.

$\endgroup$

You must log in to answer this question.

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