How to prove that $n\log n = O(n^2)$? 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?  
 A: 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}$$
A: 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)$.
A: Hints:
$$\frac{n\log n}{n^2}=\frac{\log n}n\stackrel{\text{l'Hospital, for ex.}}{\xrightarrow[n\to\infty]{}0}$$
A: 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.
A: 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!
$$
