Comparing Serveral Asymptotic Analysis Question

Question

I have the following: $n^2\log(n)$, $2^n$, $2^{2^n}$, $n^{\log(n)}$, $n^2$. In increasing order, I think their order of growth is $n^{\log(n)}$ < $n^2$ < $n^2\log(n)$ < $2^n$ < $2^{2^n}$

because I take log of all of them and found this ordering.

$n^{\log(n)} = \log(n)\log(n)$, $n^2 = 2\log(n)$, $n^2\log(n) = 2\log(n)+\log\log(n)$, $2^n = n\log(2)$, $2^{2^n} = 2^n \log(2)$

But it turns out this is wrong. Can anyone tell me what did I missed?

To me, it is not always true, for example $ n^{\log(n)} > n^2$ when $n = 1000$. Therefore, you need some conditions for $n$. — Hoping_Blessing, Jul 12 '15 at 15:33

wythagoras · Accepted Answer · 2015-07-12T19:35:46.570

2

$n^{\log(n)} > n^2 \log(n)$ for $n$ large enough. This is present in your analysis, because

$$\log(n^{\log(n)}) = (\log(n))^2 > 3\log(n) >2\log(n)+ \log(\log(n)) = n^2 \log(n)$$

if $\log(n) > 3$.

edited Jul 12 '15 at 19:35

answered Jul 12 '15 at 15:46

wythagoras

25,026

Why $log(n^{log(n)}) = log(n)^2$? – RexYuan Jul 12 '15 at 15:54
Do you mean $(log(n))^2$? – RexYuan Jul 12 '15 at 15:55
But I understand what you mean! – RexYuan Jul 12 '15 at 15:57
So the correct ordering should be $n^2$ < $n^2\log(n)$ < $n^{\log(n)}$ < $2^n$ < $2^{2^n}$, right? – RexYuan Jul 12 '15 at 15:58
@RexYuan Correct. And yes, $(\log(n))^2=\log(n)\log(n)$ was meant. – wythagoras Jul 12 '15 at 19:35

Comparing Serveral Asymptotic Analysis Question

1 Answers1