Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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
up vote 0 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|cite|improve this answer
I didn't understand the last line – Fazlan Nov 21 '12 at 16:49
@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

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|cite|improve this answer


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|cite|improve this answer

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


share|cite|improve this answer

Your Answer


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.