1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Check your maths. $\endgroup$ – gnasher729 Oct 16 '18 at 10:37
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Oct 16 '18 at 11:09
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – M a m a D Oct 16 '18 at 10:43
  • $\begingroup$ $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}$ $\endgroup$ – Apass.Jack Oct 16 '18 at 10:48
  • $\begingroup$ $n_0 = 7$ and there must be $n \geq n_0$ $\endgroup$ – M a m a D Oct 16 '18 at 10:49
  • $\begingroup$ I just edited my previous comment, in case you have not noticed. $\endgroup$ – Apass.Jack Oct 16 '18 at 10:50
  • $\begingroup$ @Noone Your maths is wrong. You made a stupid mistake in your formula (2). $\endgroup$ – gnasher729 Oct 16 '18 at 11:12
1
$\begingroup$

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.

$\endgroup$

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.