2
$\begingroup$

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}$ ??

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

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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}$?? $\endgroup$
    – Mary Star
    Jul 9, 2014 at 20:08
  • 1
    $\begingroup$ Yes, since $\dfrac{3}{n} > 0$ for all $n \ge 1$. $\endgroup$
    – JimmyK4542
    Jul 9, 2014 at 20:14
  • $\begingroup$ 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?? $\endgroup$
    – Mary Star
    Jul 9, 2014 at 20:18
  • 1
    $\begingroup$ Yes, that inequality is correct. $\endgroup$
    – JimmyK4542
    Jul 9, 2014 at 20:19
  • $\begingroup$ Great!!! Thanks a lot!!! :-) $\endgroup$
    – Mary Star
    Jul 9, 2014 at 20:19
1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ How did you find these values?? $\endgroup$
    – Mary Star
    Jul 9, 2014 at 20:20
  • $\begingroup$ 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}$. $\endgroup$
    – Did
    Jul 9, 2014 at 20:36

You must log in to answer this question.

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