In this problem we have to compare the growth rate of the following functions.
$$n^{log n}$$
$$(log n)^{n}$$
I have tried to solve this question but got stuck at a point.
My solution:
Let$$n=2^m$$
$$\therefore n^{log n}=(2^m)^{log_2 2^m}$$
$$=2^{m^{m}}$$
AND
$$(log n)^{n} = (log_2 2^m)^{2^m}$$
$$m^{2^{m}}$$
I am not able to compare between:
$$=2^{m^{m}}$$
AND
$$m^{2^{m}}$$
Please help me with this. Thank you.
Best Answer
You need to parenthesize your towers. $n^{\log n}=(2^m)^m,$ not $2^{(m^m)}$ which is the correct way to read the stack without parentheses. We are therefore comparing $$(2^m)^m \text { and } m^{(2^m)}$$ Now $(2^m)^m=2^{(m^2)}$. For large $m$ we have $$m \gt 2\\2^m \gt m^2\\m^{(2^m)} \gt (2^m)^m$$