Big $O$ estimate of $(n\log n+1)^2+ (\log n +1)(n^2+1)$

Question

Give the Big $O$ estimate of $(n \log n +1)^2 + (\log n +1)(n^2+1)$

Taking big $O$ of the first function (ignoring constant and exponent), ($n\log n + 1)^2$ we get $O (n \log n)$

Taking big $O$ of the second function (ignoring constants), $(\log n + 1) (n^2+1)$ we get $O (n^2 \log n)$.

Taking the max $(n\log n, n^2\log n) = O (n^2\log n)$ <- answer

Answer 1

We can't really ignore the exponent. Expanding the first part, we get: $$ (n\log n + 1)^2 = n^2\log^2 n + 2n\log n + 1 $$ The $n^2\log^2 n$ term dominates all other terms, so we conclude that it is $O(n^2\log^2 n)$.

Answer 2

Recall that $f(n) = O(g(n))$ iff there exists a constant $c$ and $n_{0} \in \mathbb{N}$ such that $$ f(n) \le c \cdot g(n), \quad \forall n \ge n_{0}. $$ In order to show a big-O notation complexity, it is good to think that you have to find these $c$ and $n_{0}$.

In our case, let $$ f(n) = ( n \log{n} + 1)^{2} + (\log{n} + 1)(n^{2}+1). $$ We have \begin{align} ( n \log{n} + 1)^{2} &= n^{2} \log^{2}{n} + 2 \cdot n \log{n} + 1\\ &\le n^{2} \log^{2}{n} + 3 \cdot n \log{n} \\ &\le 2 \cdot n^{2} \log^{2}{n} \end{align} where the inequalities hold for $n \ge 3$ (assuming the logarithm is base $2$). (Since the constants do not really matter, it is fine to be a little loose!)

Similarly, \begin{align} (\log{n} + 1)(n^{2}+1) &= n^{2}\log{n} + n^{2} + \log{n} + 1\\ &\le 4 \cdot n^{2}\log{n}, \end{align} for $n \ge 2$. Combining the above, we have \begin{align} f(n)&=( n \log{n} + 1)^{2} + (\log{n} + 1)(n^{2}+1) \\ &\le 2 \cdot n^{2} \log^{2}{n} + 4 \cdot n^{2}\log{n} \\ &\le 6 \cdot n^{2} \log^{2}{n}, \end{align} for $n \ge 3$. By the last inequality, we conclude that $$ f(n) = O(n^{2} \log^{2}{n}). $$