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.
Best Answer
I am familiar with the question. (I am one of the "others") I believe you neglected to specify that lg is log base 2.
In increasing order of asymptotic complexity:
$lg^2(n) = O(lg^2(n))$
$lg(2^n) = n = O(n)$
$log(2^n) = n * log(2) = O(n)$
$2^{lg(n)} = n = O(n)$
$n*log(n)+1000 = O(n log(n))$
$n^{1.1} = O(n^{1.1})$