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
Algorithms – Arrange Growth Rates in Increasing Order
algorithmsasymptotics
Related Solutions
To answer @sol4me If you know some better way then please share, i will be glad to know.
First, never trust a plot. You just saw it may hurt, so even if it can help, it's not a proof.
Then, you must know some basic comparison scales, for example, as $n\rightarrow \infty$, and fixed $a>0, b>0, c>1$ and any real $d$,
$$d \ll \log \log n \ll \log^a n \ll n^b \ll c^n \ll n! \ll n^n$$
Where I write $a_n \ll b_n$ iff $\frac{a_n}{b_n} \rightarrow 0$ (this is not a standard notation !)
Of course, there are many other possible asymptotic comparisons, these are just the most frequent.
You have also some allowed operations, for example,
- if $\xi>1$ is a fixed real and $1 \ll a_n \ll b_n$, then $\xi^{a_n} \ll \xi^{b_n}$.
- if $s_n \ll a_n$ and $s_n \ll b_n$, and if $a_n \ll b_n$, then $a_n + s_n \ll b_n + s_n$.
You prove such things by computing the limit. Taking $\log$ as you did may be very useful (for example in the first case above).
Finally, you have to apply these comparisons to your case, and sometimes it's a bit tricky, but honestly here it's not.
- $n^2 \ll 2^n$ so $2^{n^2} \ll 2^{2^n}$
- $2 \ll n$, so $2^{2^n} \ll n^{2^n}$. If in doubt, write the quotient $a_n=\left(\frac{2}{n}\right)^{2^n}$, and since $\frac{2}{n}<\frac{1}{2}$ as soon as $n>4$, you have $a_n \rightarrow 0$
- $1 \ll \log n $, so $n^2 \ll n^2 \log n$, and since $n \ll n^2$, you have $n \ll n^2\log n$.
- $n \ll n^2$ so $2^n \ll 2^{n^2}$, and also $\log n \ll n$ so $n^2 \log n \ll n^3$. Then $n^3 \ll 2^n$, hence $n^2\log n \ll n^3 \ll 2^n \ll 2^{n^2}$, and especially $n^2 \log n \ll 2^{n^2}$.
When you have a doubt, write what the comparison means as a limit, and compute the limit.
And remember, these comparisons are asymptotic. Sometimes the smallest $n$ such that the inequality really holds may be very large, but it's nevertheless only a fixed, finite number. You may have inequality for $n> 10^{10^{10}}$ for example, so trying to plot things is often hopeless.
If you want to know more about such methods, there are good readings, such as Concrete Mathematics, by Graham, Knuth and Patashnik.
Your answer is correct because $101^{16}$ is fixed in terms of growing. $n^{100}$ is slower than $1.5^{n}$. And $(n!)^{2}$ is significantly large.
Best Answer
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)$