3
$\begingroup$

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!

3 Answers 3

6

Hint: take logarithms of both of these.

  • 2
    @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$.2012-01-15
4

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

-1

Hint: Try to take n = 16. explore the behavior of the both functions with n=16, and with n > 16.