Big O, Omega, and Theta Notation Problem

Question

So I'm trying to understand a solution made by my teacher for a question that asks me to determine whether the following is true. I'm having trouble understanding where some values in the steps are coming from.

Like for the first part, I don't really get where n≥5 came from. My guess is getting 16n^2 + 25 to equal 16n^2 + n^2 by substituting n with 5. But I was wondering why 25 turned into n^2 in the first place?

I also have no idea where k = 5 came from.

For the second part of the solution, I'm also having similar struggles. Why did 16n^2 turn into 15n^2 + n^2? I'm also not sure where n≥41 and k=41 came from. I would really appreciate some clarification because I'm having trouble understanding this unit.

Answer 1

Intuitively, for all the notations in this family we only care what happens when $n$ is large. We can ignore any behavior when $n$ is small. Your teacher is choosing the breakpoint where the limiting behavior sets in. S/he wants to say that for $n$ large enough $25 \le n^2$ because that is needed for the argument. This is true as long as $n \ge 5$, which is where it comes from. S/he could have said $n \ge 10$ because there is no need to make the breakpoint as small as possible. You just need the argument to go through for all the $n$ above it.

The point of turning the $25$ into $n^2$ is to get the right side to be proportional to $n^2$ so you can invoke the definition of $O(n^2)$. We say that $f(n)\in O(n^2)$ as long as $f(n) \le cn^2$ for some fixed $c$ and $n$ large enough. The demonstration shows this works for $c=17$ as long as $n \ge 5$

Your teacher is being careful to follow the definition and show all the steps. Later on you will just say that any terms of lower order than the leading one can be ignored, so once you have $16n^2-40n+25$ you will say this is in $O(n^2)$ immediately

Answer 2

We say $f(x)=O(g(x)),$ if there exists a $k \in \mathbb{N}$ and $c \in \mathbb{R}$, s.t. for any $n\geq k$, we have $f(n)\leq c g(n)$.

for the first one, whenever $n \geq 5$, we have $5^2\leq n^2$, which gives $16n^2+25 \leq 16n^2+n^2=17n^2$, as stated by your professor. He chose $k=5$ and $c=17$, and whenever $n \geq$5, we have $f(n)\leq 17g(n) $, so by defintion $f(x)=O(g(x))$

Similarly, we say $f(x)=\Omega(g(x)),$ if there exists a $k \in \mathbb{N}$ and $c \in \mathbb{R}$, s.t. for any $n\geq k$, we have $f(n)\geq c g(n)$.

Then $f(n)=16n^2-40n+15 \geq 16n^2-40n=15n^2+n^2-40n \geq n^2-40n$ (this is because $15n^2 \geq 0$). Therefore $f(n)\geq n^2-40n=n(n-40)$. $n$ is always non-negative, therefore $f(n)$ being the product of $n$ and $n-40$ is guaranteed to be positive as long as $n-40>0$, is as long as $n\geq 41$.

Therefore $f(n)=15n^2+n^2-40n+25\geq15n^2+n^2-40n$, and $n^2-40n$ is non-negative as long as $n>41$. So for any $n>41$, we have $f(n)\geq 15n^2$, so for $c=15$, and $k=41$, we have $f(n) \geq15g(n)$, so by definition $f(n)=\Omega(n^2)$.

Put everything together to conclude that $f(n)=\Theta(n^2)$.