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.

  • 2
    $\begingroup$ Try using $a^b = e^{b \ln a}$. $\endgroup$ – Michael Biro Jan 17 '13 at 2:54
  • $\begingroup$ 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. $\endgroup$ – Ken W Jan 17 '13 at 3:01
  • $\begingroup$ Your limit for the exponential is wrong. $\endgroup$ – Amihai Zivan Jan 17 '13 at 6:06
  • $\begingroup$ What should it be then Amihai Zivan? $\endgroup$ – 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?

  • $\begingroup$ 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$. $\endgroup$ – Did Jan 17 '13 at 6:18
  • $\begingroup$ @did Thank you for pointing out that typo! $\endgroup$ – JavaMan Jan 17 '13 at 6:19
  • $\begingroup$ Awesome, thank you JavaMan for your concise explanation, and did 46 for the clarification. $\endgroup$ – Ken W Jan 17 '13 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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