1
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Jun 15 '17 at 9:12
  • 1
    $\begingroup$ Use the techniques given at our reference question. $\endgroup$ – Raphael Jun 15 '17 at 10:43
1
$\begingroup$

Firstly, your plot is wrong. See this: https://www.wolframalpha.com/input/?i=plot%5B+y%3D2%5Ex,+y%3Dx%5Elog_2(x)%5D

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

So, the answer to your first question is no. I also show you an easy proof sketch.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Jun 15 '17 at 9:15

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.