The question is,
Prove that $\frac{n^2}{2} – 3n = \Theta(n^2)$.
I understand that to do this I must determine positive constants $c_1$, $c_2$, and $n_0$ such that
$$c_1n^2 \leq \frac{n^2}{2} – 3n \leq c_2n^2$$
I simplified by dividing by $n^2$ which left
$$c_1 \leq \frac{1}{2} – \frac{3}{n} \leq c_2$$
The book I am following along with says "We can make the right-hand inequality hold for any value of $n \geq 1$ by choosing any constant $c_2 \geq \frac{1}{2}$. Likewise, we can make the left-hand inequality hold for any value of $n \geq 7$ by choosing any constant $c_1 \leq \frac{1}{14}$."
I understand that there are other choices for the constants but I'm not sure of a method for determining them. What general procedure should I use for determining these other than guess and check?
Best Answer
What you did so far was good. Then, to determine an exact choice for the constants $c_1$ and $c_2$, you should think carefully about the expression, in this case $$ \frac{1}{2} - \frac{3}{n}. $$ As $n$ gets larger, what does this sequence do? Well, it gets closer and closer to $\frac12$. And it only increases; it gets closer to $\frac12$ from below.
That means we can pick the upper bound $c_2 = \frac12$. And since it increases, we can pick the lower bound $c_1$ to be the $n$th term for some suitably large $n$. In the book, they picked $n = 7$ to get $\frac{1}{2} - \frac{3}{7} = \frac{1}{14}$ as the lower bound.