# How to order the functions based on complexity $2^n$ vs $n^{\log n}$?

How to order the functions $2^n$ vs $n^{\log n}$ based on their complexity?

I found this question in a programming website (InterviewBit). But the answer given there, $n^{\log n}, 2^n$, does not seem convincing.

The graph of the two functions also indicates that $n^{\log n}$ is more complex than $2^n$.

I also tried substituting a couple of large value for $n$ like $10^{10}$ or $10^{10000}$. They all seem to indicate that $n^{\log n}$ is more complex than $2^n$.

1. Is $n^{\log n}$ greater than $2^n$?
2. Assuming 1 is true, how to prove it without using graphs?
• Note that mathematical functions don't have complexity: they're used as a measure of complexity. (Analogy: numbers don't have height; they're used as a measure of people's height.) By plotting $x=2^y$ and $x=y^{\log y}$, you've flipped the graphs about the line $y=x$ so your plot is actually telling you the opposite of what you think they are. – David Richerby Jun 15 '17 at 9:12
• Use the techniques given at our reference question. – Raphael Jun 15 '17 at 10:43

Take the base 2 logarithm of them: $\log_2 (2^n) = n$, $\log_2 (n^{\log n}) = \log n \cdot \log_2 (n)$.
As you can see, $n$ is larger than $\log n \cdot \log_2 (n)$; therefore $2^n = \omega(n^{\log n})$.
• The plot is actually right, but it plots the functions $x=2^y$ and $x=y^{\log y}$: that is, it's flipped about the line $y=x$ from what you're expecting to see. So the plot does actually confirm that $2^n>n^{\log n}$ for the range considered. – David Richerby Jun 15 '17 at 9:15