0
$\begingroup$

I have questions with the solutions below but I'm still having trouble understanding how to solve these problems?

Like for a) I don't understand how 17$n^2$ + 4𝑛 got turned into 17$n^2$ + 4$n^2$. I also don't know what happened to the -3 for the first part of the inequality?

I'd really appreciate it if someone could walk me through the general solution of how to solve these types of questions.

enter image description here

Additionally, I was also wondering what difference would it make if the O was a Ω symbol instead? I've seen similar questions in my textbook like 4$n^2$ + 3𝑛log𝑛 + 7$n^3$ is Ω($n^3$) and was wondering what difference would this make in the solution?

$\endgroup$
  • $\begingroup$ because $4n-3\le4n\le 4n^2$ for $n\ge1$ $\endgroup$ – J. W. Tanner Apr 22 at 21:21
0
$\begingroup$

When you are working a Big-O bound, you are free to replace a term by anything larger. E.g. in $$-3+17n^2+4n$$ they replaced $-3$ by $0$ and $4n$ by $4n^2$ to get a simpler expression.

(Note that every term could have been replaced by $175n^4$ as well, giving an $O(n^4)$ bound, but this is less tight. Also note that the replacement need not be larger for all $n$, only as of some $n_0$.)

For an $\Omega$ bound, you are free to replace a term by a smaller one.

$\endgroup$
0
$\begingroup$

For a), it's not mysterious: the aim is to find a constant $C>0$ such that $\;|17n^2+4n-3|<Cn^2$ for all $n$ large enough.

First, observe the roots of $17n^2+4n-3$ are between $-1$ and $1$, so this quadratic will be positive if $n\ge 1$. So:

  1. $0<17n^2+4n-3<17n^2+4n$.
  2. Since $n\ge 1$, we have $4n \le 4n^2$, whence $0<17n^2+4n-3 < 21n^2$.

Thus a constant $C$ such that the required inequality is satisfied has been found: it is $C=21$. Of course this is not the only possible constant. Any $C>21$ will also work.

A smaller constant can be found: as $4n\le n^2$ if $n\ge4$, we have $\;17n^2+4n-3<18n^2\;$ for such $n$s.

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