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$
  • $\begingroup$ "And how can I find this c2 ??" Hmmm... $c_2=1/2$, no? $\endgroup$ – Did Aug 31 '15 at 9:48
  • $\begingroup$ Got something from an answer? $\endgroup$ – Did Aug 31 '15 at 9:48
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$
  • $\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 '14 at 20:08
  • 1
    $\begingroup$ Yes, since $\dfrac{3}{n} > 0$ for all $n \ge 1$. $\endgroup$ – JimmyK4542 Jul 9 '14 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 '14 at 20:18
  • 1
    $\begingroup$ Yes, that inequality is correct. $\endgroup$ – JimmyK4542 Jul 9 '14 at 20:19
  • $\begingroup$ Great!!! Thanks a lot!!! :-) $\endgroup$ – Mary Star Jul 9 '14 at 20:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How did you find these values?? $\endgroup$ – Mary Star Jul 9 '14 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 '14 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.