3
$\begingroup$

There are some cases where it is not so simple to decide which function grows faster asymptotically.

For example, in the following cases, why (intuitively) $g(n)$ should grow faster than $f(n)$, or vice-versa?

$$ \begin{array}{c|c} f(n) & g(n)\\ \hline 10 \log(n) & \log(n^2)\\ \frac{n^2}{\log(n)} & n(\log(n))^2\\ n^{0.1} & \log(n)^{10}\\ \log(n)^{\log(n)} & \frac{n}{\log(n)}\\ \sqrt n & \log(n)^3\\ n\,2^n & 3^n\\ \log(n)^{\log(n)} & 2^{(\log_2 n)^2} \end{array} $$

It is easy to type some values on a calculator or to plot the functions to see which one grows faster, but during an exam I cannot do this of course.

$\endgroup$
2
  • 1
    $\begingroup$ Another helpful rule of thumb: $n^k$ grows faster than $\log(n)^l$ for any fixed positive exponents $k,l$. $\endgroup$ Aug 3 '15 at 13:14
  • $\begingroup$ @KlausDraeger This is not really a rule of thumb, because it holds in any case $\endgroup$
    – tired
    Aug 3 '15 at 15:41
11
$\begingroup$

Ultimately, it suffices to evaluate the limit $$ \lim_{n \to \infty} \frac{g(n)}{f(n)} $$ if it's $\infty$, then $g$ grows faster. If it's $0$, then $f$ grows faster. If it's anything else, then they grow the same (up to some constant), i.e. $f = \Theta(g)$.

As far as intuition goes, it helps to rewrite things, or sometimes to divide/multiply both sides by the same term.

  1. Rewrite $\log(n^2) = 2 \log(n)$. It should now be obvious.

  2. Divide both sides by $\frac{n}{\log(n)}$. We're now comparing $n$ to $\log(n)^3$. $n$ is asymptotically larger since $n^\alpha$ will always beat $\log(n)^\beta$ for any $\alpha,\beta > 0$ ("polynomial beats log"). Similarly, $e^{n^\alpha}$ will always beat $n^\beta$ for any $\alpha,\beta > 0$ ("exponential beats polynomial").

  3. Same rule as last time. The left side is larger.

  4. Rewrite $\log(n)^{\log(n)} = n^{\log(\log(n))}$ (how?). Perhaps it is now clear that the left side beats $n$, let alone $\frac{n}{\log(n)}$.

  5. Polynomial always beats log (see 2.). Left is larger.

  6. Divide both sides by $2^n$. Now, the right side is larger because exponential always beats polynomial (see 2.). Right is larger.

  7. Rewrite the right side as $n^{\log_2(n)}$ (how?). This beats $n^{\log(\log(n))}$ (why)? So, the right side is larger.


Note on 4: we have $$ \log(n)^{\log(n)} = [e^{\log(\log(n))}]^{\log(n)} = e^{\log(n)\log(\log(n))} = [e^{\log(n)}]^{\log(\log(n))} = n^{\log(\log(n))} $$

$\endgroup$
1
  • 6
    $\begingroup$ @nbro: $\tfrac{3^n}{2^n}=\left(\tfrac{3}{2}\right)^n$ $\endgroup$
    – Matěj G.
    Aug 3 '15 at 13:49
1
$\begingroup$

You can use known limits such has $\lim _{n\to \infty} \frac {k^n}{n^h}=\infty \quad \forall k>1$ and $h\in \mathbb{R}$ or $\lim _{n\to \infty} \frac {n^h}{\log^k{n}}=\infty \quad \forall k> O,h\in \mathbb{R}$. For example if you compute $\frac{f(n)}{g(n)}$ from the second line you obtain $\frac{n}{\log^3{n}}$ which has infinite as limit so $f(n)$ grows faster.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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