Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

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!

share|improve this question

2 Answers

up vote 5 down vote

Hint: take logarithms of both of these.

share|improve this answer
6  
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
5  
@DavidLee: $\log$ is a monotonic function... – Fabian Jan 15 '12 at 9:04
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$. – Aaron Jan 15 '12 at 12:15
up vote 4 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.