Prove: $n\log(n^2) + (\log\ n)^2 = O(n\log(n))$

Question

Prove: $n\log(n^2) + (\log n)^2 = O(n\log(n))$

I'm trying to use the Big Oh definition, what I reached so far is:

$f(n)$ is in $O(g(n))$ if there is $M > 0,∈\mathbb{R}$ such that whenever $m > x$ we have $|f(m)|<M|(m)|$

How do I, however, continue from here?

Answer 1

Hint: Use that $\log n < n$ and $\log (n^2)=2\log n$.

Answer 2

We will take $M = 4$ and $x = e$. Then, for $n > x$, $$ \begin{align*} n \log (n^2) + (\log n)^2 &= 2n \log n + (\log n)^2 & (\because \text{Property of log})\\ &\le 2n \log n + (\sqrt{n})^2 = 2n \log n + n & (\because \log n \le \sqrt n \ \ \text{for all} \ \ n \ge 0) \\ &\le 3n \log n & (\because \log n > 1 \ \ \text{for all} \ \ n > e) \\ & < 4n \log n = M (n \log n) & \end{align*} $$ So, by definition of big-Oh notation, we are done.

Answer 3

We have that

$$n\ \log(n^2) + (\log\ n)^2 =2n\log n+\log n \cdot \log n$$

and

$$\frac{n\ \log(n^2) + (\log\ n)^2 }{n\log n}=\frac{2n\log n+\log n \cdot \log n}{n\log n}=2+\frac{\log n}n \to 2$$

therefore

$$n\ \log(n^2) + (\log\ n)^2 =O(n\log n)$$

Answer 4

You could also apply the limit definition

\begin{align}\limsup_{n\to\infty}\frac{n\log(n^2) + (\log n)^2}{n\log n}&=\limsup_{n\to\infty}\frac{2n\log n}{n\log n}+\limsup_{n\to\infty}\frac{(\log n)^2}{n\log n}\\&= \limsup_{n\to\infty} 2+\limsup_{n\to\infty}\frac{\log n}{n}\\&<\infty \end{align}

therefore $n\log(n^2) + (\log n)^2=O(n\log n)$.

Answer 5

$n\log(n^2)=2nlog n$ is $O(n\log n)$ by definition and $\log^2n=o(n\log n)$ since $$\lim_{n\to\infty}\dfrac{\log^2n}{n\log n}=\lim_{n\to\infty}\dfrac{\log n}{n }=0$$ and a fortiori, $ \log^2n=O(n\log n)$, so that $$n\log(n^2)+\log^2n=O(n\log n)+O(n\log n)=O(n\log n).$$

Answer 6

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^2} + {\log ^2}n \le c.n\log n % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaey4aIqIaam % 4yaiaacYcacaWGUbWaaSbaaSqaaiaaicdaaeqaaOGaeyOpa4JaaGim % aiaacYcacaaMe8UaaGjbVlabgcGiIiaad6gacqGHLjYScaWGUbWaaS % baaSqaaiaaicdaaeqaaOGaeyOKH4QaamOBaiGacYgacaGGVbGaai4z % aiaad6gadaahaaWcbeqaaiaaikdaaaGccqGHRaWkciGGSbGaai4Bai % aacEgadaahaaWcbeqaaiaaikdaaaGccaWGUbGaeyizImQaam4yaiaa % c6cacaWGUbGaciiBaiaac+gacaGGNbGaamOBaaaa!5A5E! $$ Lets start: $$\begin{array}{l}n\log {n^2} + {\log ^2}n \le c.n\log n \to 2n\log n + {\log ^2}n \le c.n\log n\\if\;n > 1 \to \log n > 0\\ \div \log n \to \frac{{2n\log n}}{{\log n}} + \frac{{{{\log }^2}n}}{{\log n}} \le \frac{{c.n\log n}}{{\log n}} \to 2n + \log n \le c.n\quad ;\;n > 1\;\\Let\;c = 3 \to \log n \le n\quad ;\;n > 1\end{array} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqababaaaaaaa % aapeqaa8aacaWGUbGaciiBaiaac+gacaGGNbGaamOBamaaCaaaleqa % baGaaGOmaaaakiabgUcaRiGacYgacaGGVbGaai4zamaaCaaaleqaba % GaaGOmaaaakiaad6gacqGHKjYOcaWGJbGaaiOlaiaad6gaciGGSbGa % ai4BaiaacEgacaWGUbGaeyOKH4QaaGOmaiaad6gaciGGSbGaai4Bai % aacEgacaWGUbGaey4kaSIaciiBaiaac+gacaGGNbWaaWbaaSqabeaa % caaIYaaaaOGaamOBaiabgsMiJkaadogacaGGUaGaamOBaiGacYgaca % GGVbGaai4zaiaad6gaaeaacaWGPbGaamOzaiaaysW7caWGUbGaeyOp % a4JaaGymaiabgkziUkGacYgacaGGVbGaai4zaiaad6gacqGH+aGpca % aIWaaabaGaey49aGRaciiBaiaac+gacaGGNbGaamOBaiabgkziUoaa % laaabaGaaGOmaiaad6gaciGGSbGaai4BaiaacEgacaWGUbaabaGaci % iBaiaac+gacaGGNbGaamOBaaaacqGHRaWkdaWcaaqaaiGacYgacaGG % VbGaai4zamaaCaaaleqabaGaaGOmaaaakiaad6gaaeaaciGGSbGaai % 4BaiaacEgacaWGUbaaaiabgsMiJoaalaaabaGaam4yaiaac6cacaWG % UbGaciiBaiaac+gacaGGNbGaamOBaaqaaiGacYgacaGGVbGaai4zai % aad6gaaaGaeyOKH4QaaGOmaiaad6gacqGHRaWkciGGSbGaai4Baiaa % cEgacaWGUbGaeyizImQaam4yaiaac6cacaWGUbGaaGzbVlaacUdaca % aMe8UaamOBaiabg6da+iaaigdacaaMe8oabaGaamitaiaadwgacaWG % 0bGaaGjbVlaadogacqGH9aqpcaaIZaGaeyOKH4QaciiBaiaac+gaca % GGNbGaamOBaiabgsMiJkaad6gacaaMf8Uaai4oaiaaysW7caWGUbGa % eyOpa4JaaGymaaaaaa!BCD2! $$ On the other hand, according to the function diagrams, we know: $$\log n < n\;\;;\;for\;any\;n > 0 \to \log n < n\;\;;\;n > 1 \to we\;choose\;{n_0} = 2\;optionally. % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciiBaiaac+ % gacaGGNbGaamOBaiabgYda8iaad6gacaaMe8UaaGjbVlaacUdacaaM % e8UaamOzaiaad+gacaWGYbGaaGjbVlaadggacaWGUbGaamyEaiaays % W7caWGUbGaeyOpa4JaaGimaiabgkziUkGacYgacaGGVbGaai4zaiaa % d6gacqGH8aapcaWGUbGaaGjbVlaaysW7caGG7aGaaGjbVlaad6gacq % GH+aGpcaaIXaGaeyOKH4Qaam4DaiaadwgacaaMe8Uaam4yaiaadIga % caWGVbGaam4BaiaadohacaWGLbGaaGjbVlaad6gadaWgaaWcbaGaaG % imaaqabaGccqGH9aqpcaaIYaGaaGjbVlaad+gaqaaaaaaaaaWdbiaa % dchacaWG0bGaamyAaiaad+gacaWGUbGaamyyaiaadYgacaWGSbGaam % yEaiaac6caaaa!784F! $$ So, we proved: $$c = 3,\;\;{n_0} = 2 \to \exists c,{n_0} > 0,\;\;\forall n \ge {n_0} \to n\log {n^2} + {\log ^2}n \le c.n\log n % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yaiabg2 % da9iaaiodacaGGSaGaaGjbVlaaysW7caWGUbWaaSbaaSqaaiaaicda % aeqaaOGaeyypa0JaaGOmaiabgkziUkabgoGiKiaadogacaGGSaGaam % OBamaaBaaaleaacaaIWaaabeaakiabg6da+iaaicdacaGGSaGaaGjb % VlaaysW7cqGHaiIicaWGUbGaeyyzImRaamOBamaaBaaaleaacaaIWa % aabeaakiabgkziUkaad6gaciGGSbGaai4BaiaacEgacaWGUbWaaWba % aSqabeaacaaIYaaaaOGaey4kaSIaciiBaiaac+gacaGGNbWaaWbaaS % qabeaacaaIYaaaaOGaamOBaiabgsMiJkaadogacaGGUaGaamOBaiGa % cYgacaGGVbGaai4zaiaad6gaaaa!6665! $$