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.

  • $\begingroup$ Can you compare between $2^m$ and $m^2$? $\endgroup$ – Toby Mak Feb 5 at 13:14
  • $\begingroup$ Yes. 2^m will grow faster than m^2 as it is an exponential function and m^2 is a polynomial function. $\endgroup$ – Kivtas Feb 5 at 13:21
  • $\begingroup$ $n ^{\log n} $ should be $2^{m \log_2 m}$ and $(\log n)^n$ should be $m^{(2^m)}$ $\endgroup$ – ab123 Feb 5 at 13:33
  • $\begingroup$ 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$? $\endgroup$ – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.