Compare the growth rate of given functions.

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

• Can you compare between $2^m$ and $m^2$? – Toby Mak Feb 5 at 13:14
• $n ^{\log n}$ should be $2^{m \log_2 m}$ and $(\log n)^n$ should be $m^{(2^m)}$ – ab123 Feb 5 at 13:33
• So... your goal is to compare $$2^{m^2}\qquad\text{vs.}\qquad 2^{2m\log_2m}$$ Can you at least compare $m^2$ and $2m\log_2m$? – Did Feb 5 at 14:58
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$$