Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to the book "Introduction to Algorithms" a function that has the following form
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)$.

share|cite|improve this question
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?<br/>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
@QxFFu You meant $O(n)\subset O(n^2)$. – Andreas Blass 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

2 Answers 2

up vote 0 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.