# Understanding Big O notation - discrete math?

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.

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?

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

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.

For a), it's not mysterious: the aim is to find a constant $$C>0$$ such that $$\;|17n^2+4n-3| 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.