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.

I need to show that the function $f(n) = n^2$ is not of $\mathcal{O}(n)$. If I am correct I should prove that there is no number $c,n \geq 0$ where $n^2\lt cn$. How to do that?

share|improve this question
    
It is a little hard to understand your question. Are you trying to prove that there is no $c$ such that $n^2 \leq cn$? If this is the case, you can show that there is an $n$ that violates this for any $c$. –  copper.hat Nov 21 '12 at 16:44
    
ok in simple terms how can I prove that n to the power two is not of bigO(n) –  Fazlan Nov 21 '12 at 16:45
    
@copper.hat exactly.. You are correct –  Fazlan Nov 21 '12 at 16:46
1  
If $n^2 \leq c n $ divide both sides by $n$ to get $n \leq c$. But choosing $n = \lceil c \rceil +1$ will violate this. –  copper.hat Nov 21 '12 at 16:46
add comment

4 Answers

up vote 1 down vote accepted

I assume that you want to show that $n^2 \notin \mathcal{O}(n)$. By definition, if $f(n) \in \mathcal{O}(n)$, then there exists $c>0$ such that for all $n > n_0$ we have $$f(n) \leq c n$$ If there were to exist constants $n_0$ and $c$ such that $$n^2 \leq cn$$ what happens for $n > \max \left\{n_0, c \right \}$?

share|improve this answer
    
I didn't understand the last line –  Fazlan Nov 21 '12 at 16:49
1  
@Fazlan If $n^2 \in \mathcal{O}(n)$, then there exists constant $n_0$ and $c$ such that $$n^2 \leq n$$ However, this is not possible since for any $c$, we have that for $n>c$, we get $n^2 > cn$. Hence, contradiction. –  user17762 Nov 21 '12 at 16:53
add comment

Hint:

Suppose that $n^2 = O(n)$. Then, there exist constats $C, N_0$ such that $n^2 \leq C n$ for all $ \geq N_0$. However...

share|improve this answer
add comment

$$n^2\leq cn\,\,\,\forall\,n\geq N_0\Longleftrightarrow n\leq c\,\,\,\forall n\geq N_0$$ and thus we'd get the natural numbers are bounded, say by

$$\max\{c\,,\,1,2,...,N_0-1\}$$

share|improve this answer
add comment

The result is more clear if proven directly, I think.

Let $c > 0$ be given. To conclude $n^2 \neq O(n)$, we need to produce a particular $n_0$, such that $n_0^2 > cn_0$.

To that end, choose $n_0 = c+1$. We have $$ n_0^2 = (c+1)^2 = c^2 + 2c + 1 > c^2 + c = c(c+1) = cn_0. $$

Since $c$ was arbitrary, there can be no choice of $c$ that allows $n^2 = O(n)$.

share|improve this answer
add comment

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.