0

The question is to find out which among $n^\sqrt{n}$ or $n^(log_2 n)$ is asymptotically larger? Now as a solution I read somewhere that if we take log on both sides and then compute which one is larger, it gives the same result.

Like, taking log on both sides here gives, $\sqrt{n}$ *$log_2 n$ and $(log_2 n)^2$.

Now we compute which one is larger. why taking log doesn't affect the original problem?

bandit_king28
  • 403
  • $\LaTeX$ hints: precede function names with a backslash to get the proper font. For multicharacter exponents, enclose them in braces. n^{(\log_2 n)} gives $n^{(\log_2 n)}$ – Ross Millikan Apr 18 '16 at 19:26

1 Answers1

1

Since $\log$ is increasing, we can examine the $\log$ of both the original functions to determine which one is asymptotically larger.

$\log n^{\sqrt{n}}=\sqrt{n}\log n$, while $\log(n\log n)=\log n + \log\log n\approx\log n$. Since $\sqrt{n}\log n$ is asymtotically larger than $\log n$, it follows that $n^{\sqrt{n}}$ is asymptotically larger than $n\log n$.

ervx
  • 12,208