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