I'm having a hard time figuring out what systematic approach I need to follow to solve questions like these :/ Do I expand and use the Max() principle to show that it reduces to the RHS?
Please help :(
Asked
Active
Viewed 509 times
2
-
are you familiar with quantifiers like $\exists$ and $\forall$? – Sidharth Ghoshal Sep 19 '18 at 21:27
1 Answers
1
So you would like to show $$f(n) = \Theta(n^2 \log n)$$ This means that we have to find $c_1,c_2,n_0$ for every $n \geq n_0$, we have \begin{equation} c_1 n^2 \log n \leq f(n) \leq c_2 n^2 \log n \end{equation} where \begin{equation} f(n) = (13n + 3)(9n + 1)(\log(4n^2 + 100)) \end{equation} Notice that you can write \begin{equation} f(n) =(117n^2 + 40n + 3)\log(4n^2 + 100) \end{equation} Now it is clear that for $c_1 = 1$, we have \begin{equation} f(n) \geq n^2 \log n \end{equation} This leave us to find $c_2$ and $n_0$. Assuming the $\log$ is of base $2$ (even though it could be generalized for any base), we have \begin{equation} \begin{split} f(n) &=(117n^2 + 40n + 3)\log(4n^2 + 100) \\ &\leq (117n^2 + 117n^2 + 117n^2)\log(4n^2 + 100) \\ &= 3(117n^2) \log(4n^2 + 100)\\ &\leq 3(117n^2) \log(4n^2 + 4n^2)\\ &= 351n^2 \log (8n^2)\\ &= 351n^2 \log (8) + 351n^2\log(n^2)\\ &= 3(351n^2) + 702n^2\log(n) \\ &= 1053n^2 + 702n^2\log(n) \\ &\leq 1053n^2 + 1053n^2\log(n) \\ &\leq 1053n^2\log(n) + 1053n^2\log(n) \\ &= 2016n^2\log(n) \\ &= c_2 n^2\log(n) \end{split} \end{equation} So choosing $c_2 = 2016$ for $n_0 = 2$, we get that $f(n) \leq c_2 n^2\log(n)$
Ahmad Bazzi
- 12,076