2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Sanya Nov 9 '19 at 22:26
  • 1
    $\begingroup$ @Sanya $(\log n)^2<n \log n$ $\endgroup$ – user658409 Nov 10 '19 at 4:22
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.