[Math] Does $n^{\log n}$ or $(\log n)^n$ grow faster

asymptoticslimits

Which grows faster? $n^{\log n}$ or $(\log n)^n$ and how can we prove this?

This was presented as a "challenge question" for students to try ahead of the next class meeting. Any help would be appreciated!

Best Answer

Hint: take logarithms of both of these.

Related Solutions

Calculus – How to Recognize Intuitively Which Functions Grow Faster Asymptotically

Ultimately, it suffices to evaluate the limit $$ \lim_{n \to \infty} \frac{g(n)}{f(n)} $$ if it's $\infty$, then $g$ grows faster. If it's $0$, then $f$ grows faster. If it's anything else, then they grow the same (up to some constant), i.e. $f = \Theta(g)$.

As far as intuition goes, it helps to rewrite things, or sometimes to divide/multiply both sides by the same term.

Rewrite $\log(n^2) = 2 \log(n)$. It should now be obvious.
Divide both sides by $\frac{n}{\log(n)}$. We're now comparing $n$ to $\log(n)^3$. $n$ is asymptotically larger since $n^\alpha$ will always beat $\log(n)^\beta$ for any $\alpha,\beta > 0$ ("polynomial beats log"). Similarly, $e^{n^\alpha}$ will always beat $n^\beta$ for any $\alpha,\beta > 0$ ("exponential beats polynomial").
Same rule as last time. The left side is larger.
Rewrite $\log(n)^{\log(n)} = n^{\log(\log(n))}$ (how?). Perhaps it is now clear that the left side beats $n$, let alone $\frac{n}{\log(n)}$.
Polynomial always beats log (see 2.). Left is larger.
Divide both sides by $2^n$. Now, the right side is larger because exponential always beats polynomial (see 2.). Right is larger.
Rewrite the right side as $n^{\log_2(n)}$ (how?). This beats $n^{\log(\log(n))}$ (why)? So, the right side is larger.

Note on 4: we have $$ \log(n)^{\log(n)} = [e^{\log(\log(n))}]^{\log(n)} = e^{\log(n)\log(\log(n))} = [e^{\log(n)}]^{\log(\log(n))} = n^{\log(\log(n))} $$

[Math] Which of $\log{\sqrt{n\log{n}}}$ and $\sqrt{\log{n}}$ grows faster

The first is (ignoring very small $n$) greater than $\log (n^{1/2})= \frac12 \log n$.

So setting $a = \log n$ the first is greater than $a/2$ while the latter is $\sqrt{a}$. Whence your intuition was not correct and the first grows faster.

Best Answer

Related Solutions

Calculus – How to Recognize Intuitively Which Functions Grow Faster Asymptotically

[Math] Which of $\log{\sqrt{n\log{n}}}$ and $\sqrt{\log{n}}$ grows faster

Related Question