Show that n logn is big omega(n) Solution First, n! 0 such that log (n!) > k n l

Question

Show that n logn is big omega(n)

Explanation / Answer

First, n! k n log (n) for sufficiently large n. To do that, we use a somewhat unusual method. First observe that the infinite sum 1/1^2 + 1/2^2 + 1/3^2 + ... converges to some positive constant. Let that constant be C. Then, (n!)^2 = 1^2 * 2^2 ... * n^2 > [n / (1/1^2 + 1/2^2 + ... + 1/n^2)]^n (By the GM-HM inequality) > [n / C]^n Taking logs, 2 log(n!) > n (log n) - n log C Or, log(n!) > n/2 (log n) - n/2 log C It should now be clear that any k < 1/2 will work. For example, choose k = 0.3. Then, you can easily prove that for n > C^(5/2), log(n!) > k n log n. This completes the proof. [Note that we are working with powers of 2 here. But, in fact, any power greater than 1 will work. This is because the series 1/1^m + 1/2^m + ... will converge for any m > 1. This also implies that we can choose any k < 1, which is unsurprising because n! ~ (n/e)^n for large n. The proof that n! ~ (n/e)^n is much harder, as far as I remember.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.