1

Is $3n^2 - 1$ is or is not $O(n^2)$?

I tried to solve it by adding the constants to get $c: 3 + 1 = 4; c = 4$.

If $n \geq n_0$ and $n_0$ is $1$, $3n^2 - 1 \leq 4n^2$. However, to disprove it, I tried to substitute zero to the equation:

$3n^2 - 1 \leq cn^2$

$\implies 3(0^2) - 1 \leq 4(0^2)$

$\implies 0 - 1 \leq 0$

$\implies -1 \leq 0$

So it seems that for values lower than 1, it is still true. Can someone help me to explain this?

Thanks!

user1764381
  • 113
  • Hint : Find out the limit $$\lim_{n\rightarrow \infty} \frac{3n^2-1}{n^2}$$ – Peter Aug 08 '16 at 13:02
  • You are correct that $3n^2 - 1$ is $O(n^2)$ by the method you've showed. I am not sure what you think the rest of the argument tries to show. Indeed $3n^2 - 1 < 4n^2$ for ALL n. – naslundx Aug 08 '16 at 13:07
  • @naslundx, I thought it is O(n^2) only for all n >= 1? If that's the case, then for all n < 1, it should not be O(n^2)? So if I substitute any value starting from 1 and above, 3n^2 - 1 is indeed <= 4n^2. However, if I substitute zero, I still get <=. – user1764381 Aug 08 '16 at 13:14
  • 2
    Checking what happens for $n=0$ is meaningless: the notation $O(n^2)$ is about what happens when $n$ gets larger and larger. – Bernard Aug 08 '16 at 13:14
  • @Bernard, just to clarify, in case n >=10, do you mean that it will also be meaningless to check values less than 10? – user1764381 Aug 08 '16 at 13:16
  • 2
    I suppose you mean $n_{\color{red}0}\ge 10$? Yes. Anyway, in general, the problem is not to find the best possible value for $n_0$, but to know there exists one. – Bernard Aug 08 '16 at 13:33
  • Yes @Bernard, thanks! – user1764381 Aug 08 '16 at 15:34

1 Answers1

2

$f(n) = O(n^2)$ if there exist two positive $n_0,c$ such that $$0 \le f(n) \le cn^2$$ for all $n \ge n_0$. Therefore, $3n^2-1=O(n^2)$ since one can choose $n_0 = 2, c=3$.

Bing Bang
  • 87