0
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ is there any method to choosing a c value or is it random? $\endgroup$ – lizzy_mber Sep 19 at 18:26
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 19 at 18:28
  • $\begingroup$ You miss the square of $n$ in inequality in first line, but it does not matter as it is in $\log$ function. $\endgroup$ – jaxa 9831 Sep 19 at 18:50
  • $\begingroup$ @jaxa9831 Thanks! Now fixed. $\endgroup$ – David Richerby Sep 19 at 18:58
  • $\begingroup$ @DavidRicherby Thanks! But how did you get 630n^2 log n? (in the 2nd last line) $\endgroup$ – lizzy_mber Sep 20 at 14:34
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.