Proving Big O and Big Omega of a Polynomial I have a polynomial:
$f(n)=\frac{1}{4}n^2-24n-16$
I am supposed to show that it is $\Omega(n^2)$ and $O(n^2)$. Once I prove those, it should be easy to show that it is also $\Theta(n^2)$ using the theorems given, but I'm having difficulties with $\Omega$ and $O$. Mainly the subtraction part is throwing me off, as it has been hard finding a constant and $k$ value that works.
For showing $\Omega(n^2)$, I started with $f(n)=\frac{1}{4}n^2-24n-16$ and $g(n) = n^2$, and have been trying to show that $f(n) \geq C\cdot g(n)$, but the subtraction has made it hard for me to choose a value for $C$ and $k$. Can I just chose any value that makes it work?
Pretty similar for showing $O(n^2)$, I started with $f(n)=\frac{1}{4}n^2-24n-16$ and $g(n) = n^2$, and have been trying to show that $f(n) \leq C \cdot g(n)$, and again, I'm having troubles knowing where to go from here.
 A: For checking that $f(n)$ is $O(n^2)$ I think you have just made a simple mistake and it seems like you understand what to do: if $C = \frac{1}{4}$ then $f(n) \leq C g(n)$ becomes
$$
\frac{1}{4} n^2 - 24 n - 16 \leq \frac{1}{4} n^2
$$
which is automatically always true for $n \geq 0$.
They key point for showing that $f(n)$ is $\Omega(n^2)$ is that you only need to show that there exists $C$ so that $f(n) \leq C g(n)$ for all $n$ greater than some fixed $k$. Here is how we use this fact via basically a simplifying trick: observe that for all $n \geq 1$ we have
$
6 < 24 n
$.
This means that
$$
\frac{1}{4} n^2 - 24 n - 16
\geq \frac{1}{4} n^2 - 24 n - 24 n
= \frac{1}{4} n^2 - 48 n.
$$
(In effect this means that it's enough to solve the problem for $\frac{1}{4} n^2 - 48 n$ instead.)
Moreover also note that whenever $n > 4 \times 48$ we have $\frac{1}{16} n^2 > 48 n$. That means that
$$
\frac{1}{4} n^2 - 48 n \geq \frac{1}{4} n^2 - \frac{1}{16} n^2 = \frac{3}{16} n^2 \quad \text{whenever} \quad n > 4 \times 48.
$$
Putting this all together, if we set $C = \frac{3}{16}$ then we have just shown that
$$
f(n) = \frac{1}{4} n^2 - 24 n - 16
\geq \frac{3}{16} n^2 = \frac{3}{16} g(n)
$$
for all $n > k = 4 \times 48$, which is enough to establish that $f(n)$ is $\Omega(n^2)$.
A: It is easy to show that
$$
a_n: n \mapsto \frac{{f(n)}}{{n^2 }}
$$
is an increasing sequence and $\lim_{n \to +\infty}a_n=1/4$. Thus, $a_n <1/4$ for all $n\geq 1$. Inparticular $$f(n)<\frac{1}{4}n^2$$ for all $n\geq 1$. Beacuse of the properties of $a_n$, there has to be a $k$ such that $a_n>1/10$ say, for all $n\geq k$. You can check that $k=161$ will do. Thus
$$f(n)>\frac{1}{10}n^2$$ for all $n\geq 161$.
