How to recognise intuitively which functions grow faster asymptotically?

Solution 1:

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))} $$

Solution 2:

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.