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

Show that $$\frac{1}{2}n^2-3n=\Theta{(n^2)}$$



$\displaystyle{\frac{1}{2}n^2-3n=\Theta{(n^2)}: \\ \exists c_1, c_2 >0 , \ \ \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0 \\ 0<c_1 n^2 \leq \frac{1}{2}n^2-3n \leq c_2 n^2}$



That means that I have to find the values of $n_0, c_1, c_2$ such that $$0<c_1 n^2 \leq \frac{1}{2}n^2-3n \leq c_2 n^2$$ $$\Rightarrow 0<c_1 \leq \frac{1}{2}-\frac{3}{n} \leq c_2$$

• $\displaystyle{0<c_1 \leq \frac{1}{2}-\frac{3}{n}} :$

It must be $\displaystyle{\frac{1}{2}-\frac{3}{n}>0 \Rightarrow \frac{3}{n} < \frac{1}{2} \Rightarrow n>6 \Rightarrow n \geq 7}$

So, $\displaystyle{n_1=7}$.

$\displaystyle{n \geq 7 \Rightarrow \frac{1}{7} \geq \frac{1}{n} \Rightarrow \frac{3}{7} \geq \frac{3}{n} \Rightarrow -\frac{3}{n} \geq -\frac{3}{7} \Rightarrow \frac{1}{2}-\frac{3}{n} \geq \frac{1}{2}-\frac{3}{7} \Rightarrow \frac{1}{2}-\frac{3}{n} \geq \frac{1}{14}}$

So $\displaystyle{c_1=\frac{1}{14}}$.

• $\displaystyle{\frac{1}{2}-\frac{3}{n} \leq c_2} :$

How can I find a $\displaystyle{n_2}$ such that $\displaystyle{\forall n \geq n_2:\frac{1}{2}-\frac{3}{n} \leq c_2}$ ??

And how can I find this $\displaystyle{c_2}$ ??

• "And how can I find this c2 ??" Hmmm... $c_2=1/2$, no?
– Did
Aug 31, 2015 at 9:48
• Got something from an answer?
– Did
Aug 31, 2015 at 9:48

Hint: If $n$ is non-negative (i.e. $n \ge 0$), then $\dfrac{1}{2}n^2-3n \le \dfrac{1}{2}n^2$.

This should help you find $n_2$ and $c_2$, which is what you said you are having trouble with.

• So, can I conclude to that also as follwed?? $$\frac{1}{2}-\frac{3}{n} \leq \frac{1}{2}$$ So, $\displaystyle{c_2=\frac{1}{2}}$. Is the relation $\displaystyle{\frac{1}{2}-\frac{3}{n} \leq \frac{1}{2}}$ satisfied for each $n \in \mathbb{N}$?? Jul 9, 2014 at 20:08
• Yes, since $\dfrac{3}{n} > 0$ for all $n \ge 1$. Jul 9, 2014 at 20:14
• Ahaa...Ok!! So it is as followed: $$\frac{1}{14} n^2 \leq \frac{1}{2}n^2-3n \leq \frac{1}{2} n^2, \ \ \forall n \geq n_0=\max \{1,7 \}=7$$ right?? Jul 9, 2014 at 20:18
• Yes, that inequality is correct. Jul 9, 2014 at 20:19
• Great!!! Thanks a lot!!! :-) Jul 9, 2014 at 20:19

$$n\geqslant12\implies\frac14n^2\leqslant\frac12n^2-3n\leqslant\frac12n^2$$

• How did you find these values?? Jul 9, 2014 at 20:20
• The upper bound is trivial. For the lower bound, every $c\lt\frac12$ works, for $n\geqslant n_c$, where $n_c$ solves $cn_c^2\leqslant\frac12n_c^2-3n_c$, that is, $n_c\geqslant\frac6{1-2c}$.
– Did
Jul 9, 2014 at 20:36