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

2 Answers 2

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$
5
  • $\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, 2018 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$
    – John L.
    Oct 16, 2018 at 10:48
  • $\begingroup$ $n_0 = 7$ and there must be $n \geq n_0$ $\endgroup$
    – M a m a D
    Oct 16, 2018 at 10:49
  • $\begingroup$ I just edited my previous comment, in case you have not noticed. $\endgroup$
    – John L.
    Oct 16, 2018 at 10:50
  • $\begingroup$ @Noone Your maths is wrong. You made a stupid mistake in your formula (2). $\endgroup$
    – gnasher729
    Oct 16, 2018 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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