Is $(n^{\ln n}) ∈ O((log_2(n))^n)$?

Question

Given:

• $f(n) = n ^ {ln (n)}$
• $g(n) = ( log_2n )^n$

Is $f(n) \in O(g(n))$, $g(n) \in O(f(n))$, or neither? Why?

Answer 1

Let $n=e^x$ and $p=\log_2e$ therefore $$\lim_{n\to\infty}\dfrac{f(n)}{g(n)}=\lim_{x\to\infty}\dfrac{e^{x^2}}{(px)^{e^x}}$$also we know that for large enough $x$$$\dfrac{e^{x^2}}{(px)^{e^x}}<\dfrac{e^{x^2}}{(e)^{e^x}}=e^{x^2-e^x}$$and $$\lim_{{x\to\infty}}e^{x^2-e^x}=0$$ therefore $$\lim_{n\to\infty}\dfrac{f(n)}{g(n)}=\lim_{x\to\infty}\dfrac{e^{x^2}}{(px)^{e^x}}=0$$which shows us neither $f(n) \in O(g(n))$ nor $g(n) \in O(f(n))$

Answer 2

Putting everything in the exponent, $f(n) =n ^ {ln (n)} =e^{\ln(n)\ln (n)} =e^{\ln^2(n)} $ and $g(n) = ( log_2n )^n = e^{\ln( log_2n )n} = e^{\ln( \ln(n)/ln(2 ))n} = e^{(\ln( \ln(n))-\ln(ln(2 )))n} $.

Now compare the two exponents.

Answer 3

Or just plot the functions to see the result: