# Big $\mathcal{O}$ notation problem

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?

-
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

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 \}$?

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

-

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

-

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

-