0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ $\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)}$ $\endgroup$ Apr 18 '16 at 19:26
1
$\begingroup$

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

$\endgroup$

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.