0
$\begingroup$

I want to demonstrate this relation. I know that $nlog(n)=O(n^2)$, but I would like to prove the mistake of the relation in the title using only the definition of $\Theta$. By definition, $f(n)=\Theta(g(n))$ when $$\exists c_1, c_2>0, \exists n_0 \in \mathbb{N} \mid \forall n \geq n_0 \Rightarrow c_1g(n) \leq f(n) \leq c_2g(n)$$ I don't want to use limits to verify this, only this definition. So, I need to find two constants $c_1$ and $c_2$ that satisfy the relation. In my case, I have to prove that: $$c_1n^2 \leq nlog(n) \leq c_2n^2$$ I divide the three members for $n$: $$c_1n \leq log(n) \leq c_2n$$ At this point, I would end saying that I can simply take $c_1=c_2=1$ to verify the first and second part, since I know that $n = O(log(n))$. Am I wrong? Is it enough?

$\endgroup$
  • 1
    $\begingroup$ You want to prove that the relation $f(n)=\Theta(g(n))$ is false, so you have to prove that $c_1$ and $c_2$ don't exist. In your reasoning, if $c_1=1$, you have $n\le \log n$ that is an absurd. $\endgroup$ – Exodd Jan 10 '17 at 11:35
  • $\begingroup$ @Exodd it's very similar to my idea. I worried about the fact that this could be not sufficient $\endgroup$ – Franco Scarpa Jan 10 '17 at 11:43
  • 1
    $\begingroup$ well, in fact it isn't sufficient. You have to show that for every couple $(c_1,c_2)$ your inequalities don't hold. $\endgroup$ – Exodd Jan 10 '17 at 11:45
  • $\begingroup$ @Exodd well, ok, but my question is exactly this! $\endgroup$ – Franco Scarpa Jan 10 '17 at 13:04
0
$\begingroup$

To disprove $n\log(n) = \Theta(n^2)$ you have to show

$$ \forall c_1, c_2>0, \forall n_0 \in \mathbb{N}, \exists n \geq n_0 \mid c_1n > \log(n)\, \vee \, \log(n) > c_2n $$ The second, in particular is false since $$ \lim_{n\to \infty} \frac{\log(n)}{n} =0 $$

$\endgroup$
  • $\begingroup$ I said in the description, I want only to use the definition, finding these $c_1$, $c_2$ and so on, without limits. I need a reasoning that lets me find those values. $\endgroup$ – Franco Scarpa Jan 11 '17 at 10:32
  • $\begingroup$ you can`t "find" those values since you have to prove that there are not such values $\endgroup$ – Exodd Jan 11 '17 at 10:52
  • $\begingroup$ yes, sorry. I can't use limits to prove that those values don't exist $\endgroup$ – Franco Scarpa Jan 11 '17 at 11:20

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.