3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$ ?

$\endgroup$
  • $\begingroup$ Ah! I didn't even think about trying a fraction as the constant. Now I feel like an idiot! haha. Was there any way that constant could have been found/derived without guess work? Sorry if that's a stupid question. I just want to make sure I fully understand. $\endgroup$ – AlmondMan Dec 4 '15 at 12:56
  • $\begingroup$ @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... $\endgroup$ – Orest Bucicovschi Dec 4 '15 at 13:01
  • $\begingroup$ Ah, I see, well thank you for your answer! Now I will be prepared to destroy my final exam. $\endgroup$ – AlmondMan Dec 4 '15 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.