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.
Best Answer
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)$.