Arrange the following growth rates in increasing order: $O (n (\log n)^2), O (35^n), O(35n^2 + 11), O(1), O(n \log n)$

Question

I want to Arrange the following growth rates in increasing order

This order are following : $O (n (\log n)^2), O ((35)^n), O(35n^2 + 11), O(1), O(n \log n)$

Please give me idea how to arrange growth rates in increasing order

Regards, Jatin

Answer 1

When you are talking about big O notation, you should discard the constants, which means that $O(35n^2+11)$ should be written as $O(n^2)$.

what you are interested in is the size at big numbers. And here is a rule to remember:

$$O(n^n)>O(n!)>O(\alpha^n)>O(n^\alpha)>O(log(n))>O(1)$$

Where $\alpha$ is a constant.

If you are not sure, then you can just insert a big $n$ and check which is the biggest ($n=100$):

• $35^{100} = 2.5\cdot10^{154}$

• $100^2 = 10^{4}$

• $100{\cdot}log^2(100)=400$

• $100{\cdot}log(100)=200$

• $1 = 1$ for every $n$

Showing you that $O(35^n) > O(n^2) > O(nlog^2(n))>O(nlog(n))>O(1)$

Answer 2

If

\begin{align} \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty, \end{align}

then the growth rate of $f(n)$ is larger than the growth rate of $g(n)$. Vice versa, if

\begin{align} \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0, \end{align}

then the growth rate of $f(n)$ is smaller than the growth rate of $g(n)$.

Thus, the largest growth rate is $O(35^n)$, since

\begin{align} \lim_{n \to \infty} \frac{35^n}{n \log^2 n} &= \infty, \\ \lim_{n \to \infty} \frac{35^n}{35n^2 + 11} &= \infty, \\ \lim_{n \to \infty} \frac{35^n}{1} &= \infty, \\ \lim_{n \to \infty} \frac{35^n}{n \log n} &= \infty. \end{align}

And you can do the rest yourself.