Big O notation $a*n + b = O(n^2)$

Question

According to the book "Introduction to Algorithms" a function that has the following form
$f(n)=an+b$
belong to $O(n^2)$ , and that this can be easily proven if we set
$c = a +|b|$
But I don't get it, it still seems to belong to $O(n)$.

Note big O is an upper asymptomic bound, not strict bound. So it will also fit to $O(n^5)$, $O(n^{99})$, and so on. — Studentmath, Jun 11 '14 at 15:41
It belongs in $O(n)$ and because $O(n)⊂O(n^2)$ , it belongs in $O(n^2)$ as well?
If Big-O were strict it would belong in $O(n)$ right? — QxFFu, Jun 11 '14 at 15:44
$O(n)\subset O(n^2)$ , but I am pretty sure you mean that so yes. — Studentmath, Jun 11 '14 at 15:46
@AndreasBlass Yes thats what I meant, thanks all for your fast answers. — QxFFu, Jun 11 '14 at 15:48
If it were strict it would belong there. But there is a differnt sign for strict. I've seen $\Theta$ used for strict asymptotic bounds, usually. — Studentmath, Jun 11 '14 at 15:49

score 0 · Answer 1 · answered Jun 11 '14 at 15:59

0

To be strict: $\forall n>N \ an +b <an^2 +b n^2 = (a+b)n^2 = O(n^2)$ hence the result, a very loose one of course.

answered Jun 11 '14 at 15:59

Alex

19,262

score 0 · Accepted Answer · answered Jun 11 '14 at 16:02

Everything in $O(n)$ is also $O(n^2)$. Recall that a function f(n) is O(n) if $f(n) \leq cn$ for sufficiently large $n$ and some constant $c>0$. Well, if $f(n) \leq cn$, then it's also the case that $f(n) \leq c n^2$ for all appropriately large $n$, so f(n) is $O(n^2)$ as well.

Big O notation $a*n + b = O(n^2)$

2 Answers2