# Prove that $\frac{n^2}{2} - 3n = \Theta(n^2)$

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?

• For polynomials, determining an upper constant can be done by ignoring all negative terms and increasing the order of all positive terms to match the highest ordered term. For example $10n^5-2n^4-3n^3+n^2+5n \leq 10n^5+n^2+5n\leq 10n^5+n^5+5n^5\leq 16n^5$. Finding lower bounds takes a bit more effort to explain but a similar approach can sometimes work. – JMoravitz Sep 4 '16 at 22:02

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.
Your task doesn't really require you to specify the constants. One approach for the solution would be to state that the sequence $$\frac{1}{2} - \frac{3}{n}$$ converges to the constant $\frac{1}{2}$. This means that for any $\varepsilon > 0$ there exists $N(\varepsilon)$ such that $\frac{1}{2} - \varepsilon < \frac{1}{2} - \frac{3}{n} < \frac{1}{2} + \varepsilon$ for $n > N(\varepsilon)$, which gives you the two constans for all sufficiently large $n$ (i.e. larger than $N(\varepsilon)$)