# Growth of $n^{\ln n}$ versus polynomial, exponential, and logarithmic forms

I'm attempting to clarify the proofs of these forms.

Starting with $n^{ln\,n}$ I want to compare with polynomial, exponential, and logarithmic forms.

I can understand just by looking at them which one grows faster but proving by limits using algebraic manipulation is a little more difficult.

Polynomial: $\lim_{n\to \infty} \frac{n^k}{n^{ln\,n}} = 0 \therefore n^{ln\,n} \epsilon\,\omega(n^k)$

The above seems simple enough but I'm not sure it's enough just to simplify the powers to $n^{k - ln\,n}$ to show that the limit is indeed $0$.

Exponential: $\lim_{n\to \infty} \frac{k^n}{n^{ln\,n}} = 0\therefore n^{ln\,n} \epsilon\,\omega(k^n)$

There's a trick I'm aware of that allows manipulation of exponential forms from $k^n$ into something that allows us to combine powers from the fraction, but I'm having trouble seeing it.

Logarithmic: $\lim_{n\to \infty} \frac{\ln\,n}{n^{ln\,n}} = 0\therefore n^{ln\,n} \epsilon\,\omega(\ln\,n)$

I guess I'm just looking for the algebraic manipulation to prove these growth comparisons.

• Try using $a^b = e^{b \ln a}$. – Michael Biro Jan 17 '13 at 2:54
• I agree that that's key to moving along with the exponential proof, but how would I combine exponents with the denominator? If it's not possible without using $n^n$ then I can work with that. Also I believe I can use l'hopital's rule for the Logarithmic proof. – Ken W Jan 17 '13 at 3:01
• Your limit for the exponential is wrong. – Amihai Zivan Jan 17 '13 at 6:06
• What should it be then Amihai Zivan? – Ken W Jan 17 '13 at 7:05

For polynomial and logarithmic comparisons, these should be quite clear by looking at the limit itself. With polynomial, you have $\frac{n^k}{n^{\ln n}}$. Since $k$ is fixed and $\ln n \to \infty$ as $n \to \infty$, then the limit goes to zero as you noted. With logarithmic comparison, it may help to write $$\lim_{n \to \infty} \frac{\ln n}{n^{\ln n}} = \lim_{x \to \infty} \frac{x}{e^{x^2}}$$ or even $$0 \leq \lim_{n \to \infty} \frac{\ln n}{n^{\ln n}} \leq \lim_{n \to \infty} \frac{\ln n}{n}.$$ Comparing the growth to an exponential is a little bit trickier, but not much. Just note that $k^n = e^{\ln k^n} = e^{n \ln k}$ and $n^{\ln n} = e^{(\ln n)^2}$. Which exponent grows quicker?
• Why $x/e^x$? The change of variable $x=\ln n$ yields $\ln n/n^{\ln n}=x/e^{x^2}$, not $x/e^x$. – Did Jan 17 '13 at 6:18