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?
Best Answer
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.