Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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