4
$\begingroup$

Show that $n^2 -10\notin O(n)$

My friend keeps on insisting that my proof is incorrect. Could you please tell me if there is a mistake? (made suggested edit)

Proof:

Suppose to the contrary that $n^2 -10\in O(n)$. By definition this means there exist $c >0$ and $n_0 > 0$ such that $n^2 - 10 \leq cn, \forall n>n_0$. Let $n = n_0 + c + 10$,

then $(n_0 + c + 10)^2 - 10 \leq c(n_0 + c + 10)$

$\Rightarrow$ $(n_0 + c)^2 + 2(10)(n_0+c) + 90 - cn_0 -c^2 - 10c \leq 0$

$\Rightarrow$ $(n_0^2 + 2n_0c + c^2) + 20n_0+20c + 90 - cn_0 -c^2 - 10c \leq 0$

$\Rightarrow$ $n_0^2 + n_0c + 20n_0+10c + 90 \leq 0$. Since $n_0$ and $c >0$ The left side is always greater than $0$. A contradction. Thus $n^2 -10\notin O(n)$.

  • 2
    @Mark: I had suggested change of wording at the beginning. Apart from that the structure of the argument is clearly laid out. It is formal enough by ordinary mathematical standards. And I am kind of picky.2011-10-12

2 Answers 2

3

This proof is correct. It is a bit odd - intuitively, it is not immediately obvious to me that if the identity holds for some $n_0$, then it won't hold for $n_0 + c + 10$ in particular - maybe it's just not enough?

But your proof shows that it is, and I like it because it's atypical.

  • 0
    @Mark: Nitpick: You need to mention that $c$ can be chosen to be an integer (or you take $n = n_0 +\lceil c \rceil + 10$).2013-04-21
0

This is correct. It points out the alternate case, and then proceeds to the conclusion and shows a contradiction. According to the duck test, if it swims like a duck, flies like a duck, and quacks like a duck, it is a duck. Therefore it passes the duck test. I don't see anything wrong.