How to prove that $n\log n = O(n^2)$?

Question

How to prove that $n\log n = O(n^2)$?

I think I have the idea but need some help following through.

I start by proving that if $f(n) = n \log n$ then $f(n)$ is a member of $O(n\log n)$. To show this I take a large value $k$ and show that $i\geq k$ and $f(i) \leq c_1\cdot i\log(i)$.

Next I need to show that if $f(n)$ is a member of $O(n \log n)$ then $f(n)$ is a member of $O(n^2)$ by taking a large value $k$ and showing that $i\geq k$ and $f(i) \leq c_2\cdot i\log i$ which turns out to be $f(i)=i^2\log i$ which is a member of $O(n^2)$.

Is that right? Could someone formalize this for me?

Answer 1

From your notation, it looks like we are assuming that $n\in\mathbb{N}$. In fact, I'll be more general and just say $n\in(0,\infty)$.

Then $\log n<n$, since $n < 1+n < e^n$ by its Taylor series.

Thus, $n\log n<n^2$ for all $n\in(0,\infty)$.

As a consequence, $n\log n = O(n^2)$.

Answer 2

Prove that $n\log n =O(n^2)$ is equivalent to prove that the limit $$\lim_{n\to\infty}\frac{n\log n}{n^2}=\lim_{n\to\infty}\frac{\log n}{n}$$ is finite which is the case by simple applying the l'Hôpital theorem to find that the desired limit is $0$.

Remark Since this limit is $0$ we have precisely $$n\log n= o(n^2)\quad \text{little o}$$

Answer 3

Hints:

$$\frac{n\log n}{n^2}=\frac{\log n}n\stackrel{\text{l'Hospital, for ex.}}{\xrightarrow[n\to\infty]{}0}$$

Answer 4

You only have to prove the first part. When you write $f = O(g)$ you really mean $f \in O(g)$. To prove that first part you should show that $$ \limsup \frac fg < +\infty $$ and in this case you actually have $$ \lim \frac fg = 0 $$ hence the condition is satisfied.

Answer 5

According to the formal definition of big-O, we have to show: $$\exists c,{n_0} > 0,\;\;\forall n \ge {n_0} \to n\log n \le c.{n^2} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaey4aIqIaam % 4yaiaacYcacaWGUbWaaSbaaSqaaiaaicdaaeqaaOGaeyOpa4JaaGim % aiaacYcacaaMe8UaaGjbVlabgcGiIiaad6gacqGHLjYScaWGUbWaaS % baaSqaaiaaicdaaeqaaOGaeyOKH4QaamOBaiGacYgacaGGVbGaai4z % aiaad6gacqGHKjYOcaWGJbGaaiOlaiaad6gadaahaaWcbeqaaiaaik % daaaaaaa!50F9! $$ Lets start: $$\begin{array}{l}n\log n \le c.{n^2}\\ \div n \to \log n \le c.n\\Let\;c = 1 \to \log n \le n\end{array} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGUb % GaciiBaiaac+gacaGGNbGaamOBaiabgsMiJkaadogacaGGUaGaamOB % amaaCaaaleqabaGaaGOmaaaaaOqaaiabgEpa4kaad6gacqGHsgIRci % GGSbGaai4BaiaacEgacaWGUbGaeyizImQaam4yaiaac6cacaWGUbaa % baGaamitaiaadwgacaWG0bGaaGjbVlaadogacqGH9aqpcaaIXaGaey % OKH4QaciiBaiaac+gacaGGNbGaamOBaiabgsMiJkaad6gaaaaa!5C38! $$ On the other hand, according to the function diagrams, we know: $$\log n < n\;\;;\;for\;any\;n > 0 \to we\;choose\;{n_0} = 1\;optionally. % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciiBaiaac+ % gacaGGNbGaamOBaiabgYda8iaad6gacaaMe8UaaGjbVlaacUdacaaM % e8UaamOzaiaad+gacaWGYbGaaGjbVlaadggacaWGUbGaamyEaiaays % W7caWGUbGaeyOpa4JaaGimaiabgkziUkaadEhacaWGLbGaaGjbVlaa % dogacaWGObGaam4Baiaad+gacaWGZbGaamyzaiaaysW7caWGUbWaaS % baaSqaaiaaicdaaeqaaOGaeyypa0JaaGymaiaaysW7caWGVbaeaaaa % aaaaa8qacaWGWbGaamiDaiaadMgacaWGVbGaamOBaiaadggacaWGSb % GaamiBaiaadMhacaGGUaaaaa!688B! $$ So, we proved: $$c = {n_0} = 1 \to \exists c,{n_0} > 0,\;\;\forall n \ge 1 \to n\log n \le c.{n^2} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiabg2 % da9iaad6gadaWgaaWcbaGaaGimaaqabaGccqGH9aqpcaaIXaGaeyOK % H4Qaey4aIqIaam4yaiaacYcacaWGUbWaaSbaaSqaaiaaicdaaeqaaO % GaeyOpa4JaaGimaiaacYcacaaMe8UaaGjbVlabgcGiIiaad6gacqGH % LjYScaaIXaGaeyOKH4QaamOBaiGacYgacaGGVbGaai4zaiaad6gacq % GHKjYOcaWGJbGaaiOlaiaad6gadaahaaWcbeqaaiaaikdaaaaaaa!5750! $$