Show $n\log(n^2 + constant)$ is $\in \Theta(n\log n)$

35 Views Asked by At

As mentioned in the title, I have to show that $n\log(n^2 + 21) + 11\log(n) \in \Theta(n\log n)$. I am having quite a headache over trying to split the summation in $n\log()$ and I don't really know what to do. Any advice is much appreciated.

1

There are 1 best solutions below

5
On

$$\begin{align} n\log(n^2+21) & =n\log(\mathcal O(n^2)) \\ & =n\log(\mathcal O(n)^2) \\ & =2n\log(\mathcal O(n)) \end{align}$$

$$n\log(n^2+21)+11\log(n)=2n\log(\mathcal O(n))+11\log(\mathcal O(n))=(2n+11)\log(\mathcal O(n))$$

You could also use $n^2+21<n^3$ as Joey Zou suggests, and you will get the same result.