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:

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

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

• Check your maths. – gnasher729 Oct 16 '18 at 10:37
• Where you say "A implies B", there are values where A is true but B isn't (for example c2 = 1, n = 10), so "A implies B" isn't true. Again, check your maths. (2) is obviously wrong. – gnasher729 Oct 16 '18 at 11:09

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).

• The (2) is implied by $c_1 \leq \dfrac{1}{2}-\dfrac{3}{n} \leq c_2$. What is wrong there? I dodn't fully understand your answer. explain more – M a m a D Oct 16 '18 at 10:43
• $n=10$ and $c_2=1$ satisfy $\dfrac{1}{2}-\dfrac{3}{n} \leq c_2$. However, they do not satisfy $n \leq \dfrac{1/2-c_2}{3}$ – Apass.Jack Oct 16 '18 at 10:48
• $n_0 = 7$ and there must be $n \geq n_0$ – M a m a D Oct 16 '18 at 10:49
• I just edited my previous comment, in case you have not noticed. – Apass.Jack Oct 16 '18 at 10:50
• @Noone Your maths is wrong. You made a stupid mistake in your formula (2). – gnasher729 Oct 16 '18 at 11:12

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.