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?
Best Answer
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.