How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$

I understand that essentially we have to prove that

$$c_1(n^2\log n)\le (56n^2+106n+48)(\log(264n^2+200)) \le c_2(n^2\log n)\,.$$

I am confused on how to simplify this further? And correctly find a c value.

• This is a really basic exercise. What have you tried so far apart from applying the definition of $\Theta$? – ttnick Sep 20 at 13:05
• I'm trying to learn the correct way to approach these problems. Basic for you, not for me lol. – lizzy_mber Sep 20 at 14:22

For all $$n\geq 1$$, $$56n^2+106n+48> 56n^2> n^2$$ and $$\log (264n^2+200)> \log 264n^2>\log n$$, so $$(56n^2+106n+48)\log(264n^2+200) > n^2\log n\,,$$ i.e., you can take $$c_1=1$$.

Also for all $$n\geq 1$$, $$56n^2+106n+48\leq 56n^2+106n^2+48n^2 = 210n^2$$ and, for all $$n\geq 200$$, $$264n+200 < 265n$$ so $$\log(264n^2+200) < \log 265n^2 = 2\log n + \log 265$$. For all $$n\ge 265$$, $$2\log n + \log 265\leq 3\log n$$. Therefore, for all $$n\geq 265$$, $$(56n^2+106n+48)\log(264n^2+200) < 630n^2\log n\,,$$ i.e., you can take $$c_2=630$$.

• is there any method to choosing a c value or is it random? – lizzy_mber Sep 19 at 18:26
• I just showed you how to do it. I didn't try to come up with "good" values of $c_1$ and $c_2$, but any value will do, as long as it satisfies the inequalities. – David Richerby Sep 19 at 18:28
• You miss the square of $n$ in inequality in first line, but it does not matter as it is in $\log$ function. – jaxa 9831 Sep 19 at 18:50
• @jaxa9831 Thanks! Now fixed. – David Richerby Sep 19 at 18:58
• @DavidRicherby Thanks! But how did you get 630n^2 log n? (in the 2nd last line) – lizzy_mber Sep 20 at 14:34

It's sometimes more convenient to work with the limit definitions.

To prove the statement, you can break it down into proving that $$f(n) = O(g(n))$$ and that $$f(n) = \Omega(g(n))$$. In your case, it's straightforward to compute $$\lim_{n \to \infty} f(n)/g(n)$$. I believe that this will turn out to be a positive three-digit constant less than infinity and greater than zero, and we'll be done.

$$c_1 = 56$$ works for all n.

Let n >= 265, then 200 <= $$n^2$$, $$264n^2 + 200 <= n^3$$, the logarithm is less than 3 log n, $$56n^2 + 106n + 48 <= 56n^2 + n^2 + n^2 = 58n^2$$, so you can pick \$c_2 = 58*3 = 174.