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

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)|

How do I, however, continue from here?

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

• I think one should use $\log n < n^{0.5}$ or something like that instead of $\log n < n$, because $\log n < n$ yields $(\log n)^2 < n^2$. – Sanya Nov 9 '19 at 22:26
• @Sanya $(\log n)^2<n \log n$ – user658409 Nov 10 '19 at 4:22

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)$$.

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.

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)$$

$$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).$$