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.
Asked
Active
Viewed 34 times
0
-
1One possible approach: if you can show $n^3\ge n^2+21$ for large enough $n$, then $2n\log n = n\log(n^2)\le n\log(n^2+21)\le n\log(n^3) = 3n\log n$. – Joey Zou Oct 01 '16 at 22:19
-
That was a big help, I was pulling off my hair over trying to solve it using $log(a + b) = log(a) + log(1 + b/a)$. Thanks a lot. – Clement Oct 01 '16 at 22:25
1 Answers
0
$$\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.
Simply Beautiful Art
- 74,685
-
I would avoid using using notation like $\log( \mathcal{O}(n^2))$ for basic questions like this, as it can be misleading. For example, $e^{n^2 +n} = e^{\mathcal{O}(n^2) }$ but $e^{n^2 +n}$ is not $\mathcal{O}(e^{n^2})$. – Jair Taylor Oct 01 '16 at 23:10
-
@JairTaylor Definitely true, but the taking out of the
^2is indeed possible here. $\ddot\smile$ Actually not terribly difficult to show. Think I should've perfect squared the problem? – Simply Beautiful Art Oct 01 '16 at 23:13 -
I agree the idea is kosher here, but I think you've basically absorbed the important part of the proof into the notation. – Jair Taylor Oct 01 '16 at 23:18
-
-