# Are there straightforward methods to tell which function has fastest asymptotic growth without a calculator?

For example, suppose I wanted to determine which of the following has the fastest asymptotic growth:

1. $n^2\log(n)+(\log(n))^2$

2. $n^2+\log(2^n)+1$

3. $(n+1)^3+(n-1)^3$

4. $(n+\log(n))^22^{100}$

Are there any straightforward methods to tell which is fastest without actually graphic the functions?

-

Some tips:

• Keep the following asymptotic inequalities in your head, where $f(n) \ll g(n)$ means that $\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} = 0$:$$1 \ll \log n \ll \sqrt{n} \ll n\ll n^2 \ll n^3 \ll \ldots \ll e^n \ll n!$$ and more generally, $n^a \ll n^b$ whenever $0 \leq a < b$ and $a^n \ll b^n$ whenever $1 \leq a < b$. ( I don't believe the definition I've given for $f\ll g$ is standard, so be careful using this symbol without explaining it.)

• If you are only interested in asymptotic growth, find the term in the expression that grows the fastest - then you can neglect the others. Asymptotically, they will not matter.

• Constant multipliers will not matter if one of the two functions is much larger than the other: If $f(x) \ll g(x)$ then $Cf(x) \ll g(x)$ for any $C$, no matter how larger. For example, $10^{10^{10}} n^2 \ll n^3.$

To prove a function is asymptotically faster than another, divide them. Choose the term of the two expressions that grows the fastest, and divide this by the top and bottom. Then take the limit as $n$ approaches infinity. If this is zero, the denominator is faster; if it is infinite, the numberator is faster. If the limit is a real number $x >0$ and $x<1$, then the denominator is faster, if it is $x>1$ the numerator is faster, and if it is $1$ the functions are asymptotically equal. For example, to compare (1) and (2):

$$\frac{ n^2\log(n)+(\log(n))^2}{n^2+\log(2^n)+1} = \frac{ \log(n)+\frac{(\log(n))^2}{n^2}}{1+\frac{\log(2^n)}{n^2}+\frac{1}{n^2}}$$

All of the terms in the numerator and denominator tend to $0$ except for $\log n$ and $1$ (note that $\log 2^n = n \log 2$) and so taking the limit gives $$\lim_{n \rightarrow \infty}\frac{ n^2\log(n)+(\log(n))^2}{n^2+\log(2^n)+1} = \lim_{n \rightarrow \infty} \frac{\log n}{1} = \infty$$ so the numerator is asymptotically larger.

-