Comparing Serveral Asymptotic Analysis Question

132 Views Asked by At

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?

1

There are 1 best solutions below

5
On BEST ANSWER

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