# Does $n^{\log n}$ or $(\log n)^n$ grow faster?

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!

-

## 2 Answers

Hint substitute $e^t$ in place of $n$.

-

Hint: take logarithms of both of these.

-
Does that mean comparing the growth of log f vs log g is equivalent to comparing the growth of f vs g? –  David Lee Jan 15 '12 at 8:59
@DavidLee: $\log$ is a monotonic function... –  Fabian Jan 15 '12 at 9:04
@David Lee:As Fabian says, $\log$ is a monotonic function. That means that if $f\geq g$, then $\log f \geq \log g$, and conversely. However, monotonicity alone isn't enough to preserve differences with order of growth. For example, $e^x$ and $\log$ are monotonic, and $x$ and $x^n$ have different orders of growth, but $\log x$ and $\log x^n=n\log x$ have the same order of growth, and conversely, $f$ and $nf$ have the same order of growth for any $f$, but $e^f$ and $e^{nf}=(e^f)^n$ generally do not. However, if $\log f \gg \log g$, we do have $f \gg g$. –  Aaron Jan 15 '12 at 12:15