Need help ordering a list of functions

Question

List the functions below from lowest order to highest order. If any two or more are of the same order, indicate which.

$n$, $n^3$, $2^n$, $\ln n$, $n^2$, $\ln^2 n$, $\sqrt n$, $2^{n−1}$, $\ln n$, $e^n$

I made n = 2, plugged in the values and came up with the following order:

$\ln n$, $\ln^2 n$, $\ln n$, $\sqrt n$, $n$, $2^{n-1}$, $n^2$, $2^n$, $e^n$, $n^3$

I doubt this order is correct, I just do not know. Please help.

Answer 1

If there exists limit $$ \lim_{n\to+\infty} \dfrac{f(n)}{g(n)}=C,\qquad |C|<\infty, $$

then we will assume that
functions have the same order, if $0<|C|<\infty$,
function $f(n)$ has lower order than $g(n)$, if $C=0$.

Use these well known limits:

$$ \lim_{n\to+\infty}\dfrac{\ln n}{n^a}=0, \qquad a>0; $$

$$ \lim_{n\to+\infty}\dfrac{n^a}{b^n}=0, \qquad b>1. $$

Then, for example,

$$ \lim_{n\to+\infty}\dfrac{\ln n}{\lg n}=\lim_{n\to+\infty}\dfrac{\ln n}{\ln n / \ln 10}=\ln 10\ne 0; $$

$$ \lim_{n\to+\infty}\dfrac{\ln n}{\ln^2 n}=\lim_{n\to+\infty} \dfrac{1}{\ln n}=0; $$

$$ \lim_{n\to+\infty}\dfrac{2^n}{2^{n-1}}=\lim_{n\to+\infty} 2=2\ne 0; $$

$$ \lim_{n\to+\infty}\dfrac{2^n}{e^n}=\lim_{n\to+\infty} \left(\dfrac{2}{e}\right)^n= 0. $$

So, order is as following:

• $\lg n$, $\ln n$ (they have the same order);
• $\ln^2 n$;
• $\sqrt{n}$;
• $n$;
• $n^2$;
• $n^3$;
• $2^{n-1}$, $2^n$ (they have the same order);
• $e^n$.

Answer 2

You are quite correct - your answer is wrong.

I assume that you are talking about Big O notation. To answer the question:

1. Read the article, your notes and the textbook
2. Classify the functions by the notation the fall into - to help you have some linear, polynomial, exponential, logarithmic and quasilinier.
3. Within each classification decide which will grow faster.