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?
Big $\mathcal{O}$ notation problem
-
2If $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. – 2012-11-21
4 Answers
$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\}$
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...
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 \}$?
-
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. – 2012-11-21