Trying to find $c_{1}$ , $c_{2}$ for Big theta notation.

Question

Need to find $c_{1},$ $c_{2}$ and $n_{0}$.

\begin{equation} c_{1}n^3 \leq \frac{n^3}{100} - 100n^2 - 100n + 3\leq c_{2}n^3 \end{equation}

\begin{equation} c_{1} \leq \frac{1}{100} - \frac{100}{n} - \frac{100}{n^2} + \frac{3}{n^3} \leq c_{2} \end{equation}

\begin{equation} \frac{1}{100} - \frac{100}{n} - \frac{100}{n^2} + \frac{3}{n^3} \leq c_{2} \end{equation}

This is what I have done so far, but I am currently stuck do I need to chose c2 which is positive and greater than $\frac{100}{n} + \frac{3}{n^3}$? And for c1 , I need a c1, which is >0. How do I find these constants?

Answer 1

The first step is to find a suitable $n_0.$ You know that you need $$ 0 < c_1 \leq \frac{1}{100} - \frac{100}{n} - \frac{100}{n^2} + \frac{3}{n^3} \leq c_2. $$

Ignore the $c_1$ and $c_2$ for a moment, and you may see that you need $$ 0 < \frac{1}{100} - \frac{100}{n} - \frac{100}{n^2} + \frac{3}{n^3}. $$ This must be true for every $n > n_0.$ There is no penalty for choosing $n_0$ too large. So guess big and see what happens. If you cannot show the inequality above for every $n$ greater than your guess of $n_0,$ guess bigger. Once you have a good guess you can start writing your proof.

Answer 2

As in polynomials when the variable goes to $\infty$ their behavior become like their greatest power term, so the inequality use this fact. But as $n$ becomes greater $c_1,c_2$ become more closer to $\frac{1}{100}$. Therefore if you know the bound of $n$, then you can far $c_1,c_2$ away from $\frac{1}{100}$ as it allows you.