Why is $\dfrac{1}{2}n^2-3n = \Theta(n^2)$? By definition:


  For a given function $g(n)$ we denote by $\Theta(g(n))$ the set functions
  
  $\Theta(g(n))$ = $\{f(n):$ there exists positive constants $c_1, c_2$ and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0$ .$\}$


We say $6n^3 \neq \Theta(n^2)$ becuase if it was, then there would be:

\begin{equation}
6n^3 \leq c_2n^2 \Rightarrow n \leq c_2/6  \hspace{100px} (1)
\end{equation}

which is not true because $n$ (size of the input) is not limited to any constant.

But to prove $\dfrac{1}{2}n^2-3n = \Theta(n^2)$ we can write

\begin{align*}
    c_1n^2 &amp;\leq \dfrac{1}{2}n^2-3n \leq c_2n^2\\
    c_1 &amp;\leq \dfrac{1}{2}-\dfrac{3}{n} \leq c_2
\end{align*}

by setting $c_1=1/14, c_2=1/2, n_0=7$ it becomes true.

Here is the problem, 

$$\dfrac{1}{2}-\dfrac{3}{n} \leq  c_2$$

implies

$$
n \leq \dfrac{1/2-c_2}{3} \hspace{100px} (2)
$$

why in $(1)$ bounding $n$ is a contradiction, but in $(2)$ it is not?

Thanks
Since $n&gt;0$, $\dfrac 3n &gt;0$. Hence $\dfrac{1}{2}-\dfrac{3}{n} \leq  c_2$ is implied by $\dfrac 12\le c_2$.

That is, your (2) is not correct while everything else is fine.

Just in case you cannot see why your (2) is wrong, please take a look at the following deduction.
$$ \dfrac{1}{2}-\dfrac{3}{n} \leq  c_2\\
\dfrac{1}{2}-c_2\le\dfrac{3}{n} \\
\dfrac{1/2-c_2}{3} \leq  \dfrac 1n\\
\dfrac 1n\ge\dfrac{1/2-c_2}{3} $$
Compare the last inequality with your (2).