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$

1 Answer 1

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$
3
  • $\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, 2015 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$
    – orangeskid
    Dec 4, 2015 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, 2015 at 13:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .