Order of growth for algorithms: $n^{\log(n)}$ vs. $2^n$
I am not able to determine and compare behaviour of $n^{\log(n)}$ for order of growth. If someone could help me compare it with $2^n$ with explanation that would be great.
$\endgroup$2 Answers
$\begingroup$Observe \begin{align} n^{\log n} = e^{(\log n)^2} \ \ \text{ and } \ \ 2^n = e^{n\log 2} \end{align} which means $n^{\log n}<<2^n$.
$\endgroup$ 1 $\begingroup$Another simple way can be, we can take $\log$ on both equalities. For the first one, we get $\log(2^N)=O(N)$ and for the second one, $\log(N^{\log N})= O(\log(N) *\log(N))$. Clearly first one grows faster than second one, $O(n)>O(\log(n)\log(n))$. which implies, $2^n> n^{\log(n)}$.
$\endgroup$
