1
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ "$g(n)$ is an exponential function": no, $3^{log(n)}=e^{\log(3)\log(n)}=n^{\log(3)}<n^2$. $\endgroup$
    – Yves Daoust
    Apr 18, 2022 at 14:04
  • $\begingroup$ 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 ... $\endgroup$
    – Rodrigo
    Apr 18, 2022 at 14:21
  • $\begingroup$ Your development is wrong. And what is this $1.52$ ? $\endgroup$
    – Yves Daoust
    Apr 18, 2022 at 14:26
  • $\begingroup$ 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)$. $\endgroup$
    – Rodrigo
    Apr 18, 2022 at 14:30
  • 1
    $\begingroup$ Yep. The decimal logarithm is mostly used for computation with tables, but not for common maths. $\endgroup$
    – Yves Daoust
    Apr 18, 2022 at 14:38

1 Answer 1

Reset to default
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.