1

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?

Fazlan
  • 297
  • 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
  • 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. – copper.hat Nov 21 '12 at 16:46

4 Answers4

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

Austin Mohr
  • 25,662
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...

JavaMan
  • 13,153
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 \}$?

  • 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. –  Nov 21 '12 at 16:53
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\}$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287