Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
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. –  André Nicolas Oct 12 '11 at 21:31

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
How would I express each statement in formal logic symbols? –  Mark Oct 12 '11 at 20:06
    
@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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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