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

Question

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 &\leq \dfrac{1}{2}n^2-3n \leq c_2n^2\\ c_1 &\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

Answer 1

Since $n>0$, $\dfrac 3n >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).

Answer 2

Alternatively, you might find it more convenient to work with the limit definition.

To prove that $f(n) = (1/2)n^2 - 3n = \Theta(n^2)$, we must prove that

• (i) $f(n) = O(n^2)$, and that
• (ii) $f(n) = \Omega(n^2)$.

To prove (i), we must show that $\lim_{n \to \infty} f(n)/n^2 < \infty$. Plugging in we find that $1/2 < \infty$, and are done. To prove (ii), we must show that $\lim_{n \to \infty} f(n)/n^2 > 0$. Now, we see that $1/2 > 0$, and are done. It follows from (i) and (ii) that $f(n) = \Theta(n^2)$, concluding the proof.