1
$\begingroup$

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?

  • 2
    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.2012-11-21

4 Answers 4

0

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

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

0

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

0

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