# Big Theta with Negative Coefficient Problem

I had a question in regards to solving a Big-Theta problem. Our professor wanted us to prove that $n^3 - 47n^2 + 18 = \Theta(n^3)$ and to do so rigorously, meaning he does not want us to use the below method:

$\lim\limits_{n \to \infty} \dfrac{f(n)}{g(n)} = c$

$f(n) = \Theta(g(n))$ iff $0 < c < \infty$

That being said, I did use that method just to check and ended up with $c = 1$.

So I'm using this approach instead:

$f(n) = \Theta(g(n))$ iff $f(n) = O(g(n))$ $\wedge$ $f(x) = \Omega(g(n))$

I went ahead and did Big-O and ended up deriving a constant of 1. I then reasoned that since $n - 47 \leq n$, $n^3 - 47n^2 \leq n^3$ must be true as well, proving Big-O (as far as I understand it).

The problem occurs when I try to to prove that $f(n) = \Omega(g(n))$. Using the same constant I derived earlier gets me nowhere. Because of the $-47n^2$ term, I have no idea how to prove that $n^3 - 47n^2 + 18 \geq n^3$ since it will always make $n^3 - 47n^2 + 18$ negative.

Is there something I'm missing or don't seem to understand? I'm not looking for the answer, I just need to know the correct method to go about solving this for Big-Omega. Any help would be greatly appreciated.

HINT: You should show that there exists a constant $c>0$ so that $n^3 - 47 n^2 + 18 \ge c \cdot n^3$ for $n$ sufficiently large ( won't work for all $n$ since the expression on the left is negative for $n$ below about $47$). Let's see, can you show that $$n^3 - 47 n^2 + 18 \ge \frac{3}{50} \cdot n^3$$ for $n \ge 50$ ?
• @AlmondMan: The interval ($n \ge n_0)$ for $n$ and the bound are related in a way, the larger then $n_0$ ( fewer $n$ to consider) the bigger the bound $c$ can get. Due to the existence of the limit ($=1$) it can be any $c<1$, provided that $n$ is large enough ( but cannot be $> 1$ ). The constant is derived after some fiddling ( in these standard cases), and may not be optimal... – orangeskid Dec 4 '15 at 13:01