# Is this proof of big O correct?

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

-
There are some imperfections. For example, it should start: Suppose to the contrary that $n^2 -10 \in O(n)$. By definition this means that there exists $c$, $n_0$ such that (and so on). Also, there are more efficient ways to reach a contradiction. But your proof is in essence correct. – André Nicolas Oct 12 '11 at 19:56
@AndréNicolas: I don't have the original proof with me but it has every thing you asked about. – Mark Oct 12 '11 at 19:57
@AndréNicolas: Also, my friend complains that my proof doesn't follow the formal mathematical logic of the proof by contradiction. Do you know how I should explain that it does? – Mark Oct 12 '11 at 20:03
@Mark: One usually begins by saying: assume for the sake of contradiction that " ... " And then derive a contradiction. But that's about all. – mixedmath Oct 12 '11 at 20:06
@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. – André Nicolas Oct 12 '11 at 21:31

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?
@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$). – Aryabhata Apr 21 '13 at 4:40