# Comparing two functions rate of growth

This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question.

Question. Compare the functions $$f(n) = \frac{n^2}{\log(n)}$$ and $$g(n) = 3^{\log(n)}$$ in terms of rate growth.

My attempt. I have tried to compute the limit $$\lim_{n \rightarrow +\infty} \frac{f(n)}{g(n)}$$ but this doesn't seem easy by hand. Using symbolab, it says it can't compute the limit. Obviously my intuition points towards $$f(n) << g(n)$$ just because $$g(n)$$ is an exponential function, and normally it grows faster than the polynomial ones, but I don't know how to prove this for the functions above.

Besides what I've shown above, I also tried taking $$\log$$ in both the functions, which would origin $$2\log(n) - \log(\log(n))$$ for $$f(n)$$ and $$\log(n)\log(3)$$ for $$g(n)$$ and the limit between these two is a constant which leads me to believe I cant really use this to comparate both the functions (Since my intuition tells me $$f(n) << g(n)$$, the limit I stated would be a contradiction).

So here come my two questions:

1. Can I use the $$\log$$ property above to compare two functions? I.e., does $$f(n) << g(n) \Leftrightarrow \log(f(n)) << \log(g(n))$$ ? More generally, is the comparation (of rates of growth) between $$f(n)$$ and $$g(n)$$ equivallent to comparing the rates of growth of $$\log(f(n))$$ and $$\log(g(n))$$ ?

2. How would one compare the functions from the question formally?

Thanks for any help in advance.

• "$g(n)$ is an exponential function": no, $3^{log(n)}=e^{\log(3)\log(n)}=n^{\log(3)}<n^2$.
– user16034
Apr 18, 2022 at 14:04
• I feel like this comment is better than your answer. Take a look: $g(n) = n^{\log(3)}$ and $f(n) = \frac{n^2}{\log(n)}$. Let's compute the limit. \begin{equation*} \lim_{n\rightarrow +\infty} \frac{n^{2-\log(3)}}{\log(n)} = \lim_n \frac{1.52n^{1-1.52}}{1/n} = \lim_n 1.52n^{2-1.52} = \lim_n 1.52n^{0.48} = +\infty \end{equation*} But this contradicts my intuition ... Apr 18, 2022 at 14:21
• Your development is wrong. And what is this $1.52$ ?
– user16034
Apr 18, 2022 at 14:26
• I will try to do it step by step. Here follows: \begin{equation*} \frac{f(n)}{g(n)} = \frac{\frac{n^2}{\log(n)}}{n^{\log(3)}} = \frac{n^2 \times n^{-\log(3)}}{\log(n)} = \frac{n^{2-\log(3)}}{\log(n)} = \frac{n^{1.52}}{\log(n)} \end{equation*} Where exactly is my mistake? Note: $1.52$ comes from $2-\log(3)$. Apr 18, 2022 at 14:30
• Yep. The decimal logarithm is mostly used for computation with tables, but not for common maths.
– user16034
Apr 18, 2022 at 14:38

$$\lim_{n\to\infty}\frac{n^2}{\log(n)\ 3^{\log(n)}}=\lim_{n\to\infty}\frac{n^{2-\log(3)}}{\log(n)}=\infty$$ because any positive power of $$n$$ grows faster than a logarithm.

To convince yourself, you can set $$m=\log(n)(2-\log(3))$$ and the limit is proportional to that of$$\dfrac{e^m}m$$. An exponential grows faster than any polynomial.

• This proves that $\frac{n^2}{\log(n)} >> 3^{\log(n)}$, right? Apr 18, 2022 at 14:41
• @roro Didn't you suggest this approach yourself ?
– user16034
Apr 18, 2022 at 14:43
• The answer is perfect, but my intuiton was leading me to the other way around! Guess intuition fails us sometimes :P Apr 18, 2022 at 14:45
• @roro: there are two powers of $n$, and an unimportant logarithmic factor.
– user16034
Apr 18, 2022 at 14:58