$\begingroup$

I have the following functions.

\begin{align} &7n^3 + 3n\\ &4n^2\\ &\frac{12\log(n)}{\log(n)}\\ &\frac{1}{n^2}+18n^5\\ &e^{\log\log n}\\ &2^{3n}\\ &6n\log n\\ &n!\\ \end{align}

How can I rank these functions in increasing order, by their rate of growth? Do I take a very large value of $n$ and test them for that?

What is the right approach? I can manage easy functions like $4n^2$ and $7n^3 + 3n$ -- the second has higher power of $n$, so it grows faster -- but I don't know how to handle the more complex ones.

$\endgroup$ 0

1 Answer

$\begingroup$

From slowest to fastest growth:

1. Bounded functions
2. Logarithms
3. Powers of $n$ (the greater the power, the faster)
4. Sub-exponentials: fixed base, exponent grows at a rate between logarithmic and linear
5. Exponential functions: fixed base, exponent grows at linear rate
6. Super-exponential: fixed base, exponent grows at superlinear rate. This includes $n^n = \exp(n\ln n)$ and $n! \approx \exp(n\ln(n/e))$.

From your examples:

1. $12\log(n)/\log(n)$ (simplify to see why)
2. $e^{\log\log n}$ (simplify to see why)
3. $4n^2$, $7n^3 + 3n$ and $1/(n^2)+18(n^5)$. Also $6n\log n$ which is not quite a power of $n$, but within this category: logarithm contributes less than $n^\epsilon$.
4. none
5. $2^{3n}$
6. $n!$

$\endgroup$