3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Any guess for which would be the largest and smallest growth rate? For the remaining ones, try to order them and use limits for $n \to \infty$ to assess which growth rate is bigger than the other. $\endgroup$
    – Ritz
    Commented Oct 2, 2014 at 8:21
  • $\begingroup$ no idea which was largest and smallest. $\endgroup$ Commented Oct 2, 2014 at 8:22
  • $\begingroup$ One of them stays constant when $n$ is increasing, that one might have the smallest growth rate. $\endgroup$
    – Ritz
    Commented Oct 2, 2014 at 8:23
  • $\begingroup$ i haven't idea can you give me answer? $\endgroup$ Commented Oct 2, 2014 at 8:24
  • $\begingroup$ @JatinGadhiya You need to show some working. Try substituting $n = 1, 2, \cdots$ and try to figure out the growth rates of the functions. $\endgroup$
    – taninamdar
    Commented Oct 2, 2014 at 8:32

2 Answers 2

2
$\begingroup$

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)$

$\endgroup$
2
  • 1
    $\begingroup$ Using a big $n$ might not work, since $n$ must be sufficiently large and one might not fill in a sufficiently large enough value. Think of $O(1.01^n)$ and $O(n^4)$ at $n = 1000$, where $1.01^{1000} \approx 20959$ and $1000^4 = 10^{12}$ would lead you to believe that $O(n^4) > O(1.01^n)$, but $\lim_{n \to \infty} \frac{1.01^n}{n^4} = \infty$, which correctly gives $ O(1.01^n) > O(n^4)$. I suggest an edit to the answer to be careful when one uses that approach. $\endgroup$
    – Ritz
    Commented Oct 2, 2014 at 9:54
  • $\begingroup$ You are correct with the example, that is why I gave the rule at the start which says that $O(\alpha^n)>O(n^\alpha)$ for every constant. Calculating the $lim_{n \to \infty}$can be difficult/long at some times. Putting in a number is much easier. You do need to know the "right number" to put, but usually it's not that hard to find such a number. $\endgroup$
    – SIMEL
    Commented Oct 2, 2014 at 11:16
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .